再帰で二分探索木の決まりを確かめる｜コーディング面接問題

問題

二分木の根 root を受け取ります。この木が二分探索木なら真、そうでなければ偽を返す関数を書いてください。ここでの二分探索木は、どの節についても次が成り立つ木です。

左の部分木にある値は、どれもその節の値より小さい
右の部分木にある値は、どれもその節の値より大きい
同じ値は許しません。同じ値が 2 つあれば偽です

各節は val (値)、left (左の子)、right (右の子) を持ちます。子が無いところは、Python では None、JavaScript では null、Go では nil です。Go の節は TreeNode で、Val、Left、Right と大文字で始まります。節の数は 1 以上 500 以下、値はどれも -2147483648 以上 2147483647 以下です。

例では、木を上の段から左の順に読んだ値の並びで書きます。子が無いところは null です。

入力と出力の例

例 1

根が 8、左に 3 とその下の 1 と 6、右に 12 とその下の 10 と 15 がある木です。どの節も決まりを守っています。

入力

root = [8, 3, 12, 1, 6, 10, 15]

出力

true

例 2

3 の右の子が 9 です。親の 3 より大きいので親子だけを見ると守っていますが、9 は根 8 の左の部分木にあるのに 8 より大きいので偽です。

入力

root = [8, 3, 12, 1, 9]

出力

false

例 3

左の子が根と同じ 5 です。同じ値は許さないので偽です。

入力

root = [5, 5]

出力

false

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「この二分木が、正しい二分探索木かどうかを判定してください」
親と子だけを比べる書き方を出すと、例 2 のような木を示して「これはどうなりますか？」と聞かれます
書き終えたあとに「中順 (左、自分、右の順) にたどる書き方でも書けますか？」「同じ値を左に許す決まりならどこを変えますか？」と広げて聞かれます

同じ値を許すかどうかは決まりによって違うので、最初に確かめて口に出しておきます。

アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。

まず考える手順

段 1

まず浮かぶのは、各節で「左の子は自分より小さい、右の子は自分より大きい」を確かめる書き方です。ところが、これは親と子しか見ていません。例 2 の 9 のように、親とは合っていても、もっと上の祖先との決まりを破る値を見落とします。

段 2

見方を変えます。根から下へ進むたびに、その節に入ってよい値の範囲が狭まっていきます。根はどんな値でもよく、左へ進めば「親の値より小さい」が上の限り、右へ進めば「親の値より大きい」が下の限りに加わります。この下の限りと上の限りを引数で渡していけば、祖先の決まりを全部まとめて 1 回の比べで確かめられます。

段 3

関数は (節, 下の限り, 上の限り) を受け取り、節の値が限りの間に (端は含まずに) 入っているかを見ます。入っていなければ偽、入っていれば、左の子には上の限りを自分の値に、右の子には下の限りを自分の値に替えて渡します。空の節は真です。最初の限りは、どの値よりも小さい数と大きい数にします。

段 4

別の書き方として、二分探索木を中順にたどると、値が小さい順に出てくることも使えます。たどりながら直前の値を覚え、今の値が直前の値以下になったら偽です。どちらも O(n) です。ここでは範囲を渡す書き方を解答にします。

解答

Python

def is_search_tree(root):
    inf = float("inf")
    return walk(root, -inf, inf)


def walk(n, lo, hi):
    if n is None:
        return True
    v = n.val
    if not lo < v < hi:
        return False
    if not walk(n.left, lo, v):
        return False
    return walk(n.right, v, hi)

JavaScript

function isSearchTree(root) {
  const inf = Infinity;
  return walk(root, -inf, inf);
}

function walk(n, lo, hi) {
  if (n === null) {
    return true;
  }
  const v = n.val;
  if (v <= lo || v >= hi) {
    return false;
  }
  if (!walk(n.left, lo, v)) {
    return false;
  }
  return walk(n.right, v, hi);
}

Go

import "math"

func isSearchTree(
	root *TreeNode,
) bool {
	lo := math.MinInt
	hi := math.MaxInt
	return walk(root, lo, hi)
}

func walk(
	n *TreeNode, lo, hi int,
) bool {
	if n == nil {
		return true
	}
	v := n.Val
	if v <= lo || v >= hi {
		return false
	}
	if !walk(n.Left, lo, v) {
		return false
	}
	return walk(n.Right, v, hi)
}

最初の限りは、Python と JavaScript では無限大、Go では int の最小と最大にしています。値は 32 ビットの範囲に収まるので、Go の 64 ビットの int の端とぶつかることはありません。

計算量

時間は O(n) です。どの節にも 1 回ずつ行き、限りとの比べを 1 回します
使う記憶は O(h) です。h は木の高さで、再帰の呼び出しが深さの分だけ積まれます。1 本道の木では O(n) になります。節が 500 以下なので、Python の再帰の上限 (1000 段) には届きません

よくある間違い

親と子だけを比べる。例 2 のように、親とは合っていても祖先との決まりを破る値を見落とします。範囲を上から渡すか、中順で全体の並びを見ます
限りの比べに等号を入れ忘れる。 v < lo や v > hi と書くと、例 3 のように同じ値を許してしまいます。この問題は同じ値を許さないので、v <= lo と v >= hi で偽にします
最初の限りを値の範囲の端にする。 32 ビットの最小値 -2147483648 を下の限りにすると、ちょうどその値の節が「限りと同じ」と見られて偽になります。値の範囲より外の数 (無限大や 64 ビットの端) を使います
深い木で再帰の上限に当たる。節がもっと多く 1 本道に近い木なら、Python は再帰の上限で止まります。その大きさを聞かれたら、スタックを使って中順にたどる繰り返しの書き方にすると答えます

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

def is_search_tree(root): # root の節は val、left、right を持ちます。空きは None です # ここに書きます pass # 「実行」を押すと、この行の結果が出ます # build_tree は、例と同じ並びから木を組みます print(is_search_tree(build_tree([8, 3, 12, 1, 6, 10, 15])))

再帰で二分探索木の決まりを確かめる

問題