Pythonで二分探索木（BST）の各内部ノードが子を1つだけ持つかどうかを判定する方法

問題概要

二分探索木（BST）の先行順走査（プレオーダー走査）の結果が与えられたとき、すべての内部ノードが子を1つだけ持っているかどうかを判定する問題を考えます。

たとえば、入力が preorder = [22, 12, 13, 15, 14] の場合、この先行順走査に対応するBSTは下図のようになります。すべての内部ノードが子を1つだけ持っているため、出力は True となります。

効率的な解法のポイント

ここで重要な性質があります。あるノードが子を1つだけ持つ場合、そのノードのすべての子孫は、現在のノードよりも「すべて小さい」か「すべて大きい」のどちらかに必ずなります。逆に、子を2つ持つノードが存在すれば、その子孫には現在のノードより小さいものと大きいものが混在することになります。

この性質を利用すると、以下の手順で判定できます。

• 現在のノードの直後の要素（次の先行順後続ノード）を取得する
• 先行順走査の最後の要素（最後の後続ノード）を取得する
• 両方の後続ノードが現在のノードより小さい、または両方とも大きい場合は次へ進み、そうでなければ False を返す

アルゴリズムの手順

1. 変数 next と last を 0 で初期化する
2. i を 0 から len(preorder) - 2 まで繰り返す
   • next := preorder[i] - preorder[i+1]
   • last := preorder[i] - preorder[-1]
   • もし next * last < 0 ならば False を返す（後続ノードに大小が混在している＝子を2つ持つノードが存在する）
3. ループが完了したら True を返す

この方法では配列を一度走査するだけなので、時間計算量は O(n)、追加の空間計算量は O(1) という非常に効率的なアルゴリズムになります。

実装例

def solve(preorder):
    next = 0
    last = 0
    for i in range(len(preorder) - 1):
        next = preorder[i] - preorder[i + 1]
        last = preorder[i] - preorder[-1]
        if next * last < 0:
            return False
    return True

preorder = [22, 12, 13, 15, 14]
print(solve(preorder))

入力

[22, 12, 13, 15, 14]

出力

True

まとめ

先行順走査において、「隣接要素との差」と「末尾要素との差」の積が負になる箇所が存在するかどうかを調べるだけで、BSTの全内部ノードが子を1つだけ持つかどうかを線形時間で判定できます。シンプルでありながら強力なテクニックなので、コーディング面接などでも活用できるでしょう。