LeetCode 98 - Validate Binary Search Tree

이 문제는 Medium 난이도의 BST 검증 문제다. 이진 트리의 루트가 주어졌을 때, 전체 트리가 유효한 이진 탐색 트리인지 판단해야 한다. 이번 풀이에서는 각 노드가 가질 수 있는 값의 하한과 상한을 재귀 호출로 넘기면서 검증했다.

문제 링크 & 설명

문제 링크: 98. Validate Binary Search Tree
요약: 이진 트리의 루트 노드가 주어졌을 때, 모든 노드가 BST 조건을 만족하면 true를 반환하고, 하나라도 조건을 깨면 false를 반환하는 문제다.

BST에서는 현재 노드를 기준으로 왼쪽 서브트리의 모든 값이 현재 값보다 작아야 하고, 오른쪽 서브트리의 모든 값은 현재 값보다 커야 한다. 여기서 중요한 점은 바로 아래 자식만 비교하면 부족하다는 것이다.

예를 들어 이런 트리가 있다고 해보자.

노드 7만 보면 왼쪽 자식 4는 7보다 작으므로 괜찮아 보인다. 하지만 4는 루트 5의 오른쪽 서브트리 안에 있기 때문에 5보다 커야 하고, 실제로는 4가 5보다 작으므로 이 트리는 유효한 BST가 아니다.

그래서 이 문제는 parent와 child만 비교하는 문제가 아니라, 현재 노드가 조상 노드들로부터 물려받은 전체 허용 범위 안에 있는지 확인하는 문제다.

접근 방법

처음 떠올리기 쉬운 방법은 현재 노드와 바로 아래 자식만 비교하는 방식이다.

left.val < node.val < right.val

하지만 이 조건은 local check만 한다. BST의 조건은 local condition이 아니라 subtree 전체에 걸리는 constraint다. 왼쪽 서브트리는 현재 노드보다 모두 작아야 하고, 오른쪽 서브트리는 현재 노드보다 모두 커야 한다.

그래서 재귀 호출에 현재 노드가 허용되는 범위를 함께 넘겼다. 루트는 처음에 어떤 값도 가능하므로 하한은 음의 무한대, 상한은 양의 무한대로 둔다.

lower = -inf
upper = inf

현재 노드 값이 이 범위를 벗어나면 바로 false를 반환한다.

if node.val <= lower or node.val >= upper:
    return False

그다음 왼쪽으로 내려갈 때는 현재 노드 값이 새로운 상한이 된다. 왼쪽 서브트리의 모든 값은 현재 노드보다 작아야 하기 때문이다.

left range: lower < value < node.val

반대로 오른쪽으로 내려갈 때는 현재 노드 값이 새로운 하한이 된다.

right range: node.val < value < upper

이렇게 내려가면 각 노드는 자기 부모만 보는 것이 아니라, 루트부터 현재 위치까지 이어진 모든 조상 노드의 제약을 함께 반영하게 된다.

트러블 슈팅

이 문제에서 가장 흔한 실수는 바로 아래 자식만 검사하는 것이다. 예를 들어 왼쪽 자식이 현재 노드보다 작고 오른쪽 자식이 현재 노드보다 크면 통과시키는 식이다.

if node.left and node.left.val >= node.val:
    return False
if node.right and node.right.val <= node.val:
    return False

이 코드는 다음 트리를 잡아내지 못한다.

4는 7의 왼쪽 자식이므로 7보다 작다는 조건은 만족하지만, 5의 오른쪽 서브트리에 있으므로 5보다 커야 한다는 조건은 깨고 있다. 이렇게 바로 아래 부모와만 비교하면 조상 노드의 제약을 잃어버린다.

그래서 각 재귀 호출은 현재 노드가 위치한 구간을 함께 알아야 한다. 루트의 오른쪽으로 한 번 내려간 순간부터 그 아래 모든 노드는 루트 값보다 커야 하고, 거기서 다시 왼쪽으로 내려가면 오른쪽 부모보다는 작아야 한다. 결국 각 노드는 하나의 값과 비교하는 것이 아니라 lower와 upper 사이에 있는지 검사해야 한다.

또 하나 신경 쓴 부분은 중복 값이다. LeetCode의 BST 정의에서는 왼쪽 서브트리는 현재 노드보다 strictly less, 오른쪽 서브트리는 strictly greater 조건을 만족해야 한다. 그래서 같은 값은 허용하지 않는다.

if node.val <= lower or node.val >= upper:
    return False

여기서 등호가 들어가는 이유가 그 때문이다. lower와 같거나 upper와 같으면 유효하지 않은 BST로 처리한다.

마지막으로, Python에서 min과 max는 내장 함수 이름이다. 동작은 하겠지만 변수명으로 쓰면 내장 이름을 가리게 되므로, 최종 코드에서는 lower와 upper를 사용했다.

복잡도 분석

시간 복잡도: O(n)
- 모든 노드를 최대 한 번씩 방문한다. 중간에 조건을 깨는 노드를 만나면 더 빨리 종료할 수 있지만, 최악의 경우 전체 노드를 확인해야 한다.
공간 복잡도: O(h)
- 재귀 호출 스택은 트리의 높이만큼 쌓인다. 균형 잡힌 트리라면 높이는 O(log n)이고, 한쪽으로 치우친 트리라면 O(n)까지 깊어진다.

여기서 n은 노드 수이고, h는 트리의 높이다.

구현 코드

최종 코드는 DFS로 내려가면서 각 노드 값의 가능 범위를 갱신하는 방식이다.

from typing import Optional

class Solution:
    def solve(self, node: Optional[TreeNode], lower: float, upper: float) -> bool:
        if node is None:
            return True

        if node.val <= lower or node.val >= upper:
            return False

        left = self.solve(node.left, lower, node.val)
        right = self.solve(node.right, node.val, upper)
        return left and right

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.solve(root, float('-inf'), float('inf'))

조금 더 일찍 종료하고 싶다면 왼쪽 서브트리에서 이미 false가 나온 순간 오른쪽 서브트리는 검사하지 않도록 바로 반환할 수도 있다.

from typing import Optional

class Solution:
    def solve(self, node: Optional[TreeNode], lower: float, upper: float) -> bool:
        if node is None:
            return True

        if node.val <= lower or node.val >= upper:
            return False

        return (
            self.solve(node.left, lower, node.val)
            and self.solve(node.right, node.val, upper)
        )

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.solve(root, float('-inf'), float('inf'))

두 코드의 시간복잡도 표기는 같지만, 두 번째 방식은 왼쪽 서브트리에서 이미 false가 나오면 오른쪽 서브트리를 호출하지 않는다. 전체 결과가 이미 false로 정해졌기 때문에, 남은 검사를 생략하는 방식이다.

요약 및 회고

BST 검증은 현재 노드와 자식만 비교하면 틀릴 수 있다. 각 노드는 루트부터 내려오는 동안 만들어진 lower와 upper 범위를 함께 만족해야 한다.

왼쪽으로 내려갈 때는 현재 값이 새로운 상한이 되고, 오른쪽으로 내려갈 때는 현재 값이 새로운 하한이 된다. 이 범위를 재귀 호출에 넘기면 조상 노드의 제약을 잃지 않고 전체 트리를 검증할 수 있다.

이번 문제에서 핵심은 순회 방식 자체보다, 재귀 호출이 어떤 상태를 들고 내려가야 하는지였다. BST의 구조적 조건을 lower와 upper라는 범위 상태로 바꿔서 들고 내려가면, local comparison으로 놓치는 케이스를 자연스럽게 잡을 수 있다.