이진탐색트리 확인 알고리즘 (Binary Search Tree Verification Algorithm)

 

Binary Search Tree란, 검색과 삽입을 모두 O(logN) 이라는 빠른 시간 내에 수행할 수 있는 매우 효과적인 비선형 자료구조(Non-Linear Data Structure) 이다.

 

Binary Search Tree 를 구현하는 건 어렵지않지만, 의외로 만들어져있는 트리가 BST 인지 아닌지 판별하는 알고리즘은 애를 먹는 개발자들이 많다.

 

만들어져있는 트리가 BST 인지 파악하려면 다음을 고려해야 한다.

 

1. 왼쪽 자식 노드가 루트보다 작고, 오른쪽 자식 노드가 루트보다 큰지

 

2. 왼쪽 서브트리의 최댓값이 루트보다 작고, 오른쪽 서브트리의 최솟값이 루트보다 작은지

 

문제에서 정의하는 바의 판별을 위해 간단히 재귀(Recursion) 를 이용해서 문제를 해결할 수 있다.

 

재귀적으로 트리를 Preorder Search 하면서 lower bound 와 upper bound 를 잡고, 해당 노드의 값이 그 사이에 포함되는 지를 확인해주면 된다.

 

   private boolean checkValidBST(TreeNode root, long low, long high) {
      if (root.val <= low || root.val >= high) {
         return false;
      }
      boolean result = true;
      if (root.left != null) {
         result &= checkValidBST(root.left, low, Math.min(high, root.val));
      }
      if (root.right != null) {
         result &= checkValidBST(root.right, Math.max(low, root.val), high);
      }
      return result;
   }

   public boolean isValidBST(TreeNode root) {
      if(root == null) {
         return true;
      }
      return checkValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
   }

 

위의 알고리즘을 통해 O(N) 의 복잡도에 해결해낼 수 있다.