二分木のノードは、値と最大2つの子を持ちます。木の問題の多くは同じ形をしています:左部分木について問いに答え、右部分木について答え、ノードで2つを組み合わせます。空の木が基底ケースです。
代わりにレベルについての問いもあります。それらは幅優先探索で扱います:1つのレベルのノードを保持し、すべて処理して、その子を次のレベルとして集めます。
二分探索木にはルールが1つ加わります:ノードより左にあるものはすべて小さく、右にあるものはすべて大きくなります。それを確認するにはノードとその子だけでは足りないので、進みながら許される範囲を下へ渡してください。
hを高さとすると、再帰にはO(h)のスタック領域がかかります。空の木、ノードが1つの木、片側に偏った木、負の値、そしてJavaではintの範囲を超える合計や境界をテストしてください。テストでは、木はレベルごとに書かれ、存在しない子はnullで表します。