BST の最小値と最大値

最小値を知るために、15 個すべてを見ていませんか

ただ並んでいるだけの 15 個から最小値を探すなら、15 個全部と比べるしかありません。1 個でも飛ばすと、そこに最小値がいたかもしれないからです。

木ではそうなりません。最小値がどこにいるかが、値を見る前から決まっています。

行き止まりが答え

10 の左には 5、その左には 3 がいて、3 には左の子がいません。ここで考えてみてください。3 より小さい値がこの木のどこかにあるとしたら、それは 3 の左にぶら下がっているはずです。左が空である以上、そんな値は入っていません。

だから手続きは「左へ行けなくなるまで降りる」だけで終わります。降りきったノードの値が、そのまま最小値です。最大値も同じで、今度は右へ行けなくなるまで降ります。

比較は片側 2 回、両方合わせても 4 回です。15 個を見比べる必要はどこにもありませんでした。途中の値を覚えたり比べたりする作業も要りません。降りることだけに集中します。

行き止まりの見分け方を間違える

うまくいかないときに多いのが、行き止まりの判定を「子が 1 つも無い」と書いてしまう形です。[10, 5, null, 3] という木を思い浮かべてください。10 の左が 5、5 の左が 3 で、右側には誰もいません。

最大値を探して根から右へ降りようとすると、10 には右の子がいません。ここが行き止まりなので、答えは根の 10 です。ところが「子が 1 つも無い」を条件にすると、10 は左に 5 を持っているので行き止まりと見なされず、いない右の子へ降りようとして落ちます。

見るのは進む方向の子だけです。最小を探しているなら左の子、最大なら右の子。反対側に子がいるかどうかは、この場面では関係ありません。

もう 1 つ、降りながら値を比べてしまう書き方も見かけます。「今までで一番小さかった値」を持ち回る必要はありません。着いた先が答えだと分かっているので、比較は進む方向を決めるためだけに使います。

空の木では何を返すか

ノードが 1 つも無ければ、最小も最大もありません。今回は空の配列を返す約束です。null や 0 を返すと、呼ぶ側が「値が無い」と「値が 0 だった」を区別できなくなります。

逆にノードが 1 つだけの木では、最小も最大も同じ値になります。左にも右にも降りられないので、その場の値が両方の答えです。

解説

根が答えになる形は珍しくありません。左に伸びた木では最大値が根、右に伸びた木では最小値が根です。

1. BST の最小は最左ノード、最大は最右ノードという性質を利用する
2. 戻り値は [min, max] の 2 要素配列。空木のみ空配列を返す
3. 両方の値を探すために木を全走査する必要はない (左右にだけ進む)