C++で解く二分探索木（BST）II：ノードの中間順後継を見つける方法

二分探索木（BST）の中に1つのノードが与えられたとき、そのノードの中間順巡回（in-order traversal）における後継ノードを見つける問題を考えます。中間順後継が存在しない場合はnullを返します。

ここでいう「後継ノード」とは、対象ノードの値より大きいキーの中で最小の値を持つノードのことです。

この問題の特徴として、木のルートには直接アクセスできず、対象のノードのみにアクセスできるという点があります。ただし、各ノードは親ノードへの参照（parentポインタ）を持っています。ノードの定義は以下の通りです。

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

例えば、入力が次のような木だったとします。

このとき、対象ノードが 2 であれば、出力は 3 となります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• ケース1：右の子が存在する場合

  • node を右の子に移動します。

  • その後、左の子が存在する限り、node を左の子へ移動し続けます（右部分木の最も左のノードが後継となるため）。

  • 最終的な node を返します。

• ケース2：右の子が存在しない場合

  • 「親が存在し、かつ node が親の左の子ではない」間、node を親ノードへ移動し続けます。

  • ループを抜けた時点の node の親を返します。これが中間順後継です。

このアルゴリズムの計算量は O(h)（h は木の高さ）であり、空間計算量は O(1) です。

実装例

理解を深めるために、以下の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

出力

3