C++로 구현하는 BST(이진 탐색 트리)의 중위 순회 후속자 찾기

문제 개요

이진 탐색 트리(BST)와 그 안에 있는 특정 노드가 주어졌을 때, 해당 노드의 중위 순회 후속자(in-order successor)를 찾는 문제입니다. 여기서 노드 p의 후속자란 p.val보다 큰 키 값들 중에서 가장 작은 값을 가진 노드를 의미합니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

• root = [2, 1, 3]
• p = 1

이 경우 출력은 2가 됩니다.

해결 접근 방식

BST의 성질을 활용하면 재귀 호출만으로 간단하게 문제를 해결할 수 있습니다. 단계별로 살펴보겠습니다.

1. root와 p를 매개변수로 받는 재귀 함수 inorderSuccessor()를 정의합니다.

2. root가 null이라면 null을 반환합니다.

3. root의 값이 p의 값보다 작거나 같다면, 후속자는 반드시 오른쪽 서브트리에 존재하므로 inorderSuccessor(root의 오른쪽 자식, p)를 반환합니다.

4. 그렇지 않다면(즉, root의 값이 p의 값보다 크다면), 현재 root가 후속자 후보가 됩니다. 더 작은 후보가 있는지 왼쪽 서브트리를 탐색합니다.

   • option := inorderSuccessor(root의 왼쪽 자식, p)
   • option이 null이면 root를 반환하고, 그렇지 않으면 option을 반환합니다.

C++ 구현 예제

다음 구현을 통해 동작 방식을 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = NULL;
        right = NULL;
    }
};
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(!root) return NULL;
        if(root->val <= p->val){
            return inorderSuccessor(root->right, p);
        }
        else{
            TreeNode* option = inorderSuccessor(root->left, p);
            return !option ? root : option;
        }
    }
};
main(){
    TreeNode *root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    TreeNode *p = root->left;
    Solution ob;
    cout << (ob.inorderSuccessor(root, p))->val;
}

입력

{2,1,3},1

출력

2

동작 원리와 시간 복잡도

이 알고리즘은 BST의 핵심 성질, 즉 "왼쪽 서브트리의 모든 노드는 루트보다 작고, 오른쪽 서브트리의 모든 노드는 루트보다 크다"는 특성을 활용합니다. 현재 노드의 값이 목표 노드 p의 값보다 작거나 같으면 후속자는 오른쪽에만 존재하고, 반대로 현재 노드의 값이 더 크다면 현재 노드가 후속자 후보가 되며 왼쪽 서브트리에서 더 작은 후보를 계속 찾아 내려갑니다.

시간 복잡도는 트리의 높이 h에 비례하여 O(h)입니다. 따라서 균형 잡힌 BST에서는 O(log n), 최악의 경우(편향된 트리)에는 O(n)이 됩니다. 공간 복잡도 역시 재귀 호출 스택의 깊이만큼인 O(h)입니다.