C# 재귀 함수로 이진 트리가 유효한 이진 탐색 트리(BST)인지 검증하는 방법

이진 탐색 트리(Binary Search Tree, BST)는 모든 왼쪽 자식 노드가 부모 노드보다 작고, 모든 오른쪽 자식 노드가 부모 노드보다 큰 값을 가지는 트리 구조입니다. 이 글에서는 C#의 재귀(Recursion)를 활용하여 주어진 이진 트리가 유효한 이진 탐색 트리인지 확인하는 방법을 알아보겠습니다.

검증 알고리즘의 핵심 원리

유효성 검사는 다음과 같은 순서로 진행됩니다.

먼저 현재 노드에 값이 존재하는지 확인합니다. 노드가 null이라면 더 이상 검사할 대상이 없으므로 유효한 이진 탐색 트리로 간주하고 true를 반환합니다.

노드가 null이 아닌 경우, 최솟값(min)과 최댓값(max)을 함께 전달하며 재귀 메서드 isValidBST를 호출합니다. 각 단계에서 루트 값이 허용 범위를 벗어나는지, 즉 루트 값이 min보다 작거나 같거나 max보다 크거나 같은지 검사합니다. 범위를 벗어난다면 해당 트리는 이진 탐색 트리가 아니므로 false를 반환합니다.

범위 내에 있다면 왼쪽 서브트리에는 현재 노드의 값을 새로운 max로, 오른쪽 서브트리에는 현재 노드의 값을 새로운 min으로 전달하면서 isValidBST를 재귀적으로 호출합니다. 이 과정을 모든 노드를 검사할 때까지 반복하며, 좌우 서브트리의 결과가 모두 true일 때만 최종적으로 true를 반환합니다.

C# 구현 예제 코드

public class TreesPgm{
    public class Node{
        public int Value;
        public Node LeftChild;
        public Node RightChild;
        public Node(int value){
            this.Value = value;
        }
        public override String ToString(){
            return "Node=" + Value;
        }
    }
    public bool isValidBST(Node root){
        if (root == null){
            return true;
        }
        return isValidBST(root, int.MinValue, int.MaxValue);
    }
    private bool isValidBST(Node root, int min, int max){
        if (root == null){
            return true;
        }
        if (root.Value <= min || root.Value >= max){
            return false;
        }
        return isValidBST(root.LeftChild, min, root.Value) && isValidBST(root.RightChild,
        root.Value, max);
    }
}

동작 예시

다음과 같은 트리를 입력으로 넣어 보겠습니다.

   5
  2 6
1  3

루트 노드는 5이고, 왼쪽 자식으로 2와 그 아래 1, 3이 있으며 오른쪽 자식으로 6이 있는 구조입니다. 모든 왼쪽 자식(2, 1)은 부모보다 작고, 오른쪽 자식(6, 3)은 부모보다 크므로 이 트리는 유효한 이진 탐색 트리입니다.

출력 결과

True

정리

이 알고리즘은 각 노드마다 허용 가능한 값의 범위(min, max)를 상속해 내려가는 방식으로 동작하기 때문에, 단순히 부모와 자식 관계만 비교하는 방식보다 정확합니다. 예를 들어 루트의 오른쪽 서브트리 깊숙한 곳에 있는 노드가 루트 값보다 작아지는 경우도 min/max 범위 검사를 통해 올바르게 걸러낼 수 있습니다. 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)이며, 재귀 호출 깊이는 트리의 높이에 비례합니다.