C++로 이진 탐색 트리(BST)에서 중위 순회 후속자(In-order Successor) 찾기

문제 개요

이진 탐색 트리(Binary Search Tree, BST) 안의 한 노드가 주어졌을 때, 해당 노드의 중위 순회 후속자(in-order successor)를 찾는 문제를 살펴보겠습니다. 중위 순회 후속자란 현재 노드의 값보다 큰 키를 가진 노드들 중에서 가장 작은 값을 가진 노드를 의미합니다. 만약 후속자가 존재하지 않는다면 null을 반환하면 됩니다.

이 문제의 핵심 제약 조건은 트리의 루트(root)에는 접근할 수 없고, 주어진 노드에만 직접 접근이 가능하다는 점입니다. 대신 각 노드는 자신의 부모 노드에 대한 참조(pointer)를 가지고 있으므로, 이를 활용해 문제를 해결해야 합니다.

노드 정의

class Node {
   public int val;
   public Node left;
   public Node right;
   public Node parent;
}

예시

다음과 같은 트리가 있다고 가정해 보겠습니다.

C++로 이진 탐색 트리(BST)에서 중위 순회 후속자(In-order Successor) 찾기

여기서 값이 2인 노드가 입력으로 주어지면, 출력은 3이 됩니다. 2보다 큰 값들(3, 4, 5, 6) 중 가장 작은 값이 3이기 때문입니다.

풀이 접근 방법

이 문제는 두 가지 경우로 나누어 생각할 수 있습니다.

경우 1: 오른쪽 자식이 존재하는 경우

현재 노드의 오른쪽 서브트리가 존재한다면, 후속자는 반드시 오른쪽 서브트리 안에 있습니다. 먼저 오른쪽 자식으로 이동한 뒤, 왼쪽 자식이 더 이상 없을 때까지 계속 왼쪽으로 내려가면 도달한 노드가 바로 후속자입니다. 이는 오른쪽 서브트리에서 중위 순회 시 가장 먼저 방문되는 노드이기 때문입니다.

경우 2: 오른쪽 자식이 없는 경우

오른쪽 자식이 없다면, 조상 노드들 중에서 현재 노드가 왼쪽 자식인 지점을 찾아야 합니다. 부모를 따라 계속 위로 올라가면서 "현재 노드가 부모의 왼쪽 자식인가?"를 확인하고, 그러한 부모를 처음 만나는 순간 그 부모가 후속자가 됩니다. 루트까지 올라가도 찾지 못한다면 후속자가 존재하지 않으므로 null을 반환합니다.

알고리즘 단계 정리

노드의 오른쪽 자식이 null이 아니라면:
- node := node의 오른쪽 자식
- node의 왼쪽 자식이 null이 아닌 동안 반복:
  - node := node의 왼쪽 자식
- node 반환
그렇지 않다면, node의 부모가 null이 아니고 node가 부모의 왼쪽 자식이 아닌 동안 반복:
- node := node의 부모
node의 부모 반환

C++ 구현 예제

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
   int val;
   Node* left;
   Node* right;
   Node* parent;
   Node(int v, Node* par = NULL){
      val = v;
      left = NULL;
      right = NULL;
      parent = par;
   }
};
class Solution {
public:
   Node* inorderSuccessor(Node* node) {
      if (node->right) {
         node = node->right;
         while (node->left)
         node = node->left;
         return node;
      }
      while (node->parent && node != node->parent->left) {
         node = node->parent;
      }
      return node->parent;
   }
};
main(){
   Solution ob;
   Node *root = new Node(5);
   root->left = new Node(3, root);
   root->right = new Node(6, root);
   root->left->left = new Node(2, root->left);
   root->left->right = new Node(4, root->left);
   root->left->left->left = new Node(1, root->left->left);
   cout << (ob.inorderSuccessor(root->left->left))->val;
}

입력

Node *root = new Node(5);
root->left = new Node(3, root);
root->right = new Node(6, root);
root->left->left = new Node(2, root->left);
root->left->right = new Node(4, root->left);
root->left->left->left = new Node(1, root->left->left);
(ob.inorderSuccessor(root->left->left))->val