繰り返しで二分探索木に新しい値を葉として足す｜コーディング面接問題

問題

二分探索木の根 root と、木にまだ無い整数 val を受け取ります。val を持つ節を新しく作って木に足し、足したあとの木の根を返す関数を書いてください。

二分探索木では、どの節でも、左の部分木の値はすべてその節より小さく、右の部分木の値はすべてその節より大きくなっています
足し方は 1 つに決めます。根から、val が節より小さければ左、大きければ右へ進み、子の無い所に出たら、そこへ新しい節を葉としてつなぎます。木の形を組み替えてはいけません
各節は val、left、right を持ちます。Go の節は TreeNode で、Val、Left、Right です。新しい節は、Python では TreeNode(val)、JavaScript では new TreeNode(val) で作れます。Go では TreeNode を作り、そのアドレスを使います (解答の初めの数行を見てください)
root が空の木のこともあります。そのときは、val の節 1 つだけの木を返します
節の数は 0 以上 500 以下です。値はどれも違い、val も含めて -100000000 以上 100000000 以下です

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

入力と出力の例

例 1

50 は 40 より大きいので右の 60 へ進み、60 より小さいので 60 の左の空きに入ります。

入力

root = [40, 20, 60, 10, 30]
val = 50

出力

[40, 20, 60, 10, 30, 50]

例 2

同じ木に 35 を足します。40 の左、20 の右と進み、30 の右の空きに入ります。

入力

root = [40, 20, 60, 10, 30]
val = 35

出力

[40, 20, 60, 10, 30, null, null,
  null, null, null, 35]

例 3

空の木です。新しい節が、そのまま根になります。

入力

root = []
val = 3

出力

[3]

面接での聞かれ方

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

「二分探索木に値を 1 つ足して、根を返してください」
「足し方は何通りもありますが、いちばん素直な形でかまいません」と言われ、葉として足す形を選べるかを見られます
書き終えたあとに「再帰でも書けますか？」「同じ値を何度も足すと、木はどうなりますか？」と聞かれます

木の問題では、どの位置につなぐかを先に口で言っておくと、聞き手も追いやすくなります。

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

まず考える手順

段 1

まず、値を探すときと同じ道を考えます。二分探索木では、val が今の節より小さければ左、大きければ右へ進みます。val は木に無いので、いつか子の無い所に行き当たります。

段 2

行き当たった空きこそ、val を置いてよい場所です。そこまでの道で、val は通った節それぞれと大小を比べて正しい側へ進んできたので、葉として置いても決まりは崩れません。木の残りは 1 つも動かさずに済みます。

段 3

空きにつなぐには、その 1 つ上の節 (親) が要ります。進むたびに「今の節」を親として覚えておき、今の節が空になったら、覚えておいた親の左か右に新しい節をつなぎます。左右のどちらかは、val と親の値の大小で決まります。

段 4

返すのは元の根のままです。新しい節は必ず葉として下に付くので、根は変わりません。ただし木が空のときだけは、つなぐ先の親がいないので、新しい節そのものを根として返します。再帰で書くこともできますが、1 本道を下るだけなので、繰り返しで書くと呼び出しの積み重ねも要りません。

解答

Python

def insert_bst(root, val):
    leaf = TreeNode(val)
    if root is None:
        return leaf
    parent = root
    node = root
    while node:
        parent = node
        if val < node.val:
            node = node.left
        else:
            node = node.right
    if val < parent.val:
        parent.left = leaf
    else:
        parent.right = leaf
    return root

JavaScript

function insertBst(root, val) {
  const leaf =
    new TreeNode(val);
  if (root === null) {
    return leaf;
  }
  let parent = root;
  let node = root;
  while (node !== null) {
    parent = node;
    node = val < node.val
      ? node.left
      : node.right;
  }
  if (val < parent.val) {
    parent.left = leaf;
  } else {
    parent.right = leaf;
  }
  return root;
}

Go

func insertBst(
	root *TreeNode, val int,
) *TreeNode {
	leaf := &TreeNode{Val: val}
	if root == nil {
		return leaf
	}
	parent := root
	node := root
	for node != nil {
		parent = node
		if val < node.Val {
			node = node.Left
		} else {
			node = node.Right
		}
	}
	if val < parent.Val {
		parent.Left = leaf
	} else {
		parent.Right = leaf
	}
	return root
}

parent は、node が空になる直前に通った節です。繰り返しを抜けたとき、node は空なので、もう子をつなげません。そこで 1 つ手前の parent を覚えておき、その左か右につなぎます。

計算量

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

よくある間違い

空の木を見落とす。 root が空なのに親をたどり始めると、空の節の val を読んで止まります。最初に、新しい節をそのまま返します
空きに出たあとで、つなぐ先を失う。 node を空になるまで進めると、つなぐべき親がもう手元にありません。進む前に親を覚えておくか、子が空かを 1 つ手前で確かめます
根に近い所へ割り込ませる。値の大小だけを見て途中の節の間に差し込むと、その下の部分木との大小が崩れます。葉として足せば、どの比べ方も変わりません
左右の向きを逆に比べる。 val < node.val で右へ進むと、決まりと逆の側に付きます。足したあとの木を中順に読み、小さい順になっているかで確かめられます
再帰で書いて戻り値を入れ直さない。再帰で書くときは「足したあとの部分木の根」を返し、root.left や root.right に入れ直します。入れ直さないと、作った節がどこにもつながりません

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

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

繰り返しで二分探索木に新しい値を葉として足す

問題