[자료구조] 이진 탐색 트리 (BST)

1일 1코딩테스트를 풀어보려고 노력하고 있습니다.

Leetcode에서 진행 중이며 금일 푼 문제에서 이진 탐색 트리 문제가 있어 정리를 해보고자 작성합니다.

 

이진 탐색 트리

이진 탐색 트리란 정렬된 이진트리로 다음과 같은 속성을 가지고 있다.

1. Root 노드 왼쪽에는 해당 노드의 값보다 작은 값의 노드만 포함 된다.
2. Root 노드 오른쪽에는 해당 노드의 값보다 큰 값의 노드만 포함된다.
3. 왼쪽, 오른쪽 하위 노드도 각각 이진 검색 트리여야 한다.
4. 중복된 키는 허용하지 않는다

 

[leetcode] 700 .  Search in a Binary Search Tree 문제 참조

 

 

문제는 다음과 같습니다.

 

You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

 

우리의 친구 구글 번역기를 통해 한번 번역을 해보면

 

"BST와 어떤 정수 값이 주어지면 해당 BST에서 정수 값과 같은 노드를 찾아 하위 트리까지 같이 반환을 하라는 문제입니다."

 

그럼 저 문제를 어떤 방식으로 풀어 볼 수 있을까요?

 

문제의 해답은 처음에 말씀 드렸던 BST의 특성에 있습니다.

BST의 경우 Root 노드의 값이 있고 다음부터 입력 되는 값들은 해당 Root 노드보다 작은지 또는 큰지에 따라 왼쪽, 오른쪽으로 저장되는 위치가 정해집니다.

그럼 아래와 같이 풀어볼 수 있겠죠?

 

1. BST를 탐색하기 위해 while문으로 loop 처리를 한다.
2. BST의 값을 꺼내서 주어진 정수와 비교한다.
   1. 값이 같으면 바로 return을 하던지 값을 담아서 break처리를 한다.
   2. 노드의 값이 주어진 정수 보다 크면 left로 이동
   3. 노드의 값이 주어진 정수 보다 작으면 right로 이동
3. 일치하는 값이 없으면 null을 return

 

코드는 아래와 같습니다.

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode treeNode = null;

        while (root != null) {
            if (root.val == val) {
                treeNode = root;
                break;
            } else if (root.val < val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }

        return treeNode;
    }
}

(TreeNode 객체는 leetcode에서 제공되는 객체 입니다.)

 

테스트 통과