C++で二分探索木（BST）の中間順後継ノード（Inorder Successor）を求める方法

問題の概要

二分探索木（BST）と、その木に含まれるあるノードが与えられたとき、そのノードの「中間順後継（In-order Successor）」を探索する問題を考えてみましょう。

ここでいうノード p の後継とは、「p.val よりも大きいキーの中で最小の値を持つノード」のことを指します。

例

入力が root = [2,1,3]、p = 1 の場合を考えてみます。

この場合、出力は 2 となります。値1の次に大きい値は2だからです。

解法のアプローチ

この問題は、BSTの性質を利用した再帰的なアプローチで効率よく解くことができます。手順は以下の通りです。

• 再帰メソッド inorderSuccessor() を定義します。引数としてルートノード root と対象ノード p を受け取ります。
• root が NULL の場合は、NULL を返します。
• root の値が p の値以下の場合、後継は右部分木に存在するため、inorderSuccessor(root の右部分木, p) の結果を返します。
• それ以外の場合（root の値が p の値より大きい場合）：
  • option := inorderSuccessor(root の左部分木, p) を求めます。
  • option が NULL であれば現在の root を、そうでなければ option を返します。

このアルゴリズムでは、各ステップで探索範囲が半分に絞られていくため、平衡なBSTであれば計算量は O(log n)、最悪の場合でも O(n) で処理できます。

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 以下なら右へ、大きければ左へ進みつつ候補を記録する」という再帰的な考え方は、他のBST関連の問題にも応用できる重要なテクニックなので、ぜひマスターしておきましょう。