二分探索木の大小で 2 つの節の共通の祖先を探す｜コーディング面接問題

問題

二分探索木の根 root と、木の中にある 2 つの値 p、q を受け取ります。値が p の節と値が q の節の両方を子孫に持つ節のうち、いちばん深い節 (共通の祖先) を探し、その節の値を返す関数を書いてください。

二分探索木では、どの節でも、左の部分木の値はすべてその節より小さく、右の部分木の値はすべてその節より大きくなっています
節は自分自身の子孫にも数えます。片方の節がもう片方の祖先なら、上にある方が答えです
各節は val、left、right を持ちます。Go の節は TreeNode で、Val、Left、Right です
節の数は 2 以上 500 以下です。値はどれも違い、-1000000000 以上 1000000000 以下です。p と q は違う値で、どちらも必ず木の中にあります。p と q のどちらが小さいかは決まっていません

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

入力と出力の例

例 1

5 と 15 は、どちらも 20 より小さいので 20 の左にあります。10 の所で左右に分かれるので、10 が答えです。

入力

root = [20, 10, 30, 5, 15, 25,
  40]
p = 5
q = 15

出力

例 2

3 は 2 の右、6 は 4 の右にあります。4 から見ると 3 は左、6 は右なので、4 で分かれます。

入力

root = [8, 4, 12, 2, 6, 10, 14,
  1, 3]
p = 6
q = 3

出力

例 3

40 は 30 の右の子です。30 自身が 40 の祖先なので、30 が答えです。

入力

root = [50, 30, 70, null, 40]
p = 30
q = 40

出力

面接での聞かれ方

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

「二分探索木で、2 つの値の共通の祖先を返してください」
ふつうの二分木と同じ書き方 (両側を全部たどる) を答えると、「二分探索木であることを使えますか？」と聞き返されます
「片方がもう片方の祖先のときはどうなりますか？」と、端の場合を口で確かめられます

ふつうの二分木の版と二分探索木の版は、聞かれ方が似ていて答えの速さが違います。どちらを聞かれているかを、最初に確かめておきます。

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

まず考える手順

段 1

まず素直な書き方を考えます。根から p までの道と q までの道をそれぞれ集め、前から見て最後に一致した節が答えです。答えは合いますが、道を 2 本覚えるので、木の高さ分の記憶を使います。

段 2

二分探索木の決まりを使います。今の節より p も q も小さければ、2 つとも左の部分木にあるので、答えも左にあります。2 つとも大きければ右です。それ以外、つまり今の節が 2 つの値の間にあるか、どちらかと等しいなら、2 つはここで左右に分かれるか、ここ自身が片方なので、今の節が答えです。

段 3

小さい方と大きい方を先に決めておくと、比べ方が短くなります。大きい方が今の節より小さければ左へ、小さい方が今の節より大きければ右へ進み、どちらでもなければ今の節の値を返します。p と q は必ず木にあるので、空の節に行き当たる前に必ず答えが見つかります。

解答

Python

def common_ancestor(root, p, q):
    lo = min(p, q)
    hi = max(p, q)
    node = root
    while True:
        if hi < node.val:
            node = node.left
        elif lo > node.val:
            node = node.right
        else:
            return node.val

JavaScript

function commonAncestor(
  root, p, q
) {
  const lo = Math.min(p, q);
  const hi = Math.max(p, q);
  let node = root;
  while (true) {
    if (hi < node.val) {
      node = node.left;
    } else if (lo > node.val) {
      node = node.right;
    } else {
      return node.val;
    }
  }
}

Go

func commonAncestor(
	root *TreeNode, p, q int,
) int {
	lo, hi := p, q
	if lo > hi {
		lo, hi = hi, lo
	}
	node := root
	for {
		if hi < node.Val {
			node = node.Left
		} else if lo > node.Val {
			node = node.Right
		} else {
			return node.Val
		}
	}
}

「今の節が 2 つの値の間にある」場合と「今の節がどちらかと等しい」場合は、どちらも最後の else に入ります。分けて書かなくても、例 3 のように片方が祖先の場合まで正しく扱えます。

計算量

時間は O(h) です。h は木の高さです。根から答えの節まで、1 本道を下るだけです。木が片側に伸びきると h は n になり、O(n) です
使う記憶は O(1) です。lo、hi、node の 3 つの置き場だけを使い、再帰の呼び出しも積みません

よくある間違い

p と q の大小を決めつける。 p が小さい方だと思い込んで p < node.val と q > node.val で分けると、例 2 のように p の方が大きい入力で道を間違えます。先に小さい方と大きい方を決めます
等しい場合を下へ進めてしまう。 <= で比べると、今の節が p そのものなのに、さらに下へ進んで答えを通り過ぎます。等しいときはその節が答えです
二分探索木の決まりを使わない。ふつうの二分木と同じく両側を全部たどると、答えは合いますが O(n) かかり、面接では「決まりを使えていない」と見られます
節を返してしまう。この問題で返すのは節の値です。節そのものを返すと比べられません

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

def common_ancestor(root, p, q): # root の節は val、left、right を持ちます。空きは None です # ここに書きます pass # 「実行」を押すと、この行の結果が出ます # build_tree は、例と同じ並びから木を組みます print(common_ancestor(build_tree([20, 10, 30, 5, 15, 25, 40]), 5, 15))

二分探索木の大小で 2 つの節の共通の祖先を探す

問題