C++でBST（二分探索木）の先行順巡回結果からルートより小さい要素の数を求める方法

この記事では、BST（二分探索木）の先行順巡回（プレオーダートラバーサル）の結果が与えられたときに、ルート（根）よりも小さい要素の個数を求める方法を解説します。

先行順巡回には「配列の最初の要素が必ずBSTのルートになる」という重要な性質があります。この性質を利用すれば、木を実際に構築しなくても効率的に答えを求められます。まずは具体例を見てみましょう。

問題の例

入力

preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]

出力

3

ルートは配列の先頭にある「5」です。ルートより小さい要素は「4」「2」「1」の3つなので、答えは3になります。

アルゴリズム

• 先行順巡回の結果を配列として用意します。

• 配列の先頭要素（BSTのルート）を変数に保存します。

• 配列の2番目の要素から順にループで走査します。

  • 各要素とルートを比較します。

  • 現在の要素がルートより小さければ、カウントを1増やします。

• 最後にカウントを返します。

このアルゴリズムは配列を一度だけ走査するため、時間計算量はO(n)、追加のメモリはO(1)で済むという効率の良さが特徴です。

C++での実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;

int getElementsCount(int arr[], int n) {
    if (n <= 0) {
        return 0;
    }
    int root = arr[0], count = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] < root) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
    int n = 8;
    cout << getElementsCount(preorder, n) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

3

まとめ

先行順巡回の「先頭要素がルートになる」という性質を利用すれば、BSTを構築することなく、ルートより小さい要素の数を線形時間O(n)で簡単に求められます。配列を一巡してルートと比較するだけなので、実装も非常にシンプルです。