[DSA][Trees] 11. Validate Binary Search Tree

LeetCode 98

 

11. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.

 

 

[질문하기]

- 노드 값에 중복이 있을 수 있나요?

- 트리가 비어 있을 경우 True를 반환하나요?

 

[아이디어]

- 각 노드가 가질 수 있는 값의 범위 (min, max)를 추적하자.

 

 

[풀이 1] Depth First Search

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, left, right):
            if not node:
                return True
            if not (left < node.val < right):
                return False

            return valid(node.left, left, node.val) and valid(node.right, node.val, right)

        return valid(root, float("-inf"), float("inf"))

BST는 다음 조건을 만족해야 한다.

• 왼쪽 서브트리의 모든 값 < 현재 노드 값
• 오른쪽 서브트리의 모든 값 > 현재 노드 값

 

위 조건을 만족하는지 확인하기 위해, 각 노드가 가질 수 있는 값의 범위 (min, max)를 인자로 넘겨서
node.val 이 이 범위 내에 있는지를 검사한다. 자식 노드를 재귀적으로 탐색할 때, 왼쪽 서브트리는 현재 노드보다 작아야 하므로 max 값을 node.val로 설정하고 오른쪽 서브트리는 현재 노드보다 커야 하므로 min 값을 node.val로 설정하여 호출한다.

이 과정을 루트 노드에서 시작하여 모든 노드에 적용하면, 트리가 BST 조건을 만족하는지 확인할 수 있다.

 

⏱️ 시간복잡도

트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되기 때문에 O(h)에 비례하고 따라서 공간 복잡도는 최악의 경우 O(N) (Skew 트리)이고, 평균적으로는 O(log N) (균형 잡힌 트리)이다.