スタックの中順の走査で二分探索木の k 番目に小さい値を探す｜コーディング面接問題

問題

二分探索木の根 root と、整数 k を受け取ります。木の値を小さい順に並べたとき、前から数えて k 番目 (1 から数える) の値を返す関数を書いてください。

二分探索木では、どの節でも、左の部分木の値はすべてその節より小さく、右の部分木の値はすべてその節より大きくなっています
各節は val、left、right を持ちます。Go の節は TreeNode で、Val、Left、Right です
節の数を n とすると、n は 1 以上 500 以下、k は 1 以上 n 以下です。値はどれも違い、-10000 以上 10000 以下です
木を再帰でたどらず、自分で用意したスタックを使った繰り返しで書いてください

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

入力と出力の例

例 1

小さい順に並べると 1、3、4、6、9、11 です。3 番目は 4 です。

入力

root = [6, 3, 9, 1, 4, null,
  11]
k = 3

出力

例 2

2 の右に 3 がぶら下がった木です。小さい順は 2、3、5、8 で、4 番目は 8 です。

入力

root = [5, 2, 8, null, 3]
k = 4

出力

例 3

節が 1 つだけの木です。

入力

root = [7]
k = 1

出力

面接での聞かれ方

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

「二分探索木の中で、k 番目に小さい値を返してください」
値を全部集めて並べ替える書き方を答えると、「二分探索木の決まりを使えていますか？」「k が小さいとき、全部読む必要がありますか？」と聞き返されます
「再帰を使わずに書けますか？」と、繰り返しの書き方を求められることもあります

二分探索木の問題では、「左、自分、右の順に読むと小さい順になる」と最初に言えるかで、その先の会話が変わります。

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

まず考える手順

段 1

まず素直な書き方を考えます。木の値を全部集めて小さい順に並べ替え、k - 1 番目を返します。答えは合いますが、全部を集めて並べ替えるので O(n log n) かかり、二分探索木の決まりも使っていません。

段 2

二分探索木では、左の部分木、自分、右の部分木の順に読むと (中順の走査)、値が小さい順に出てきます。左はどれも自分より小さく、右はどれも自分より大きいからです。この順に読みながら数え、k 個目に出てきた値を返せば、並べ替えは要りません。k 個目で止めるので、後ろは読まずに済みます。

段 3

中順の走査を、再帰の代わりにスタックで書きます。今の節から左へ行けるだけ進み、通った節をスタックに積みます。行き止まったら 1 つ取り出し、それが次に小さい値です。数え終わっていなければ、取り出した節の右の子へ移り、また左へ進むことを繰り返します。

段 4

スタックに積んだ節は、「左の部分木を読み終えたら読む節」の予約です。再帰で書いたときに呼び出しの積み重ねが覚えていたことを、自分のスタックが代わりに覚えています。こうすると、木が片側に深く伸びていても、言語の再帰の上限を気にせずに済みます。

解答

Python

def kth_in_bst(root, k):
    stack = []
    node = root
    while True:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

JavaScript

function kthInBst(root, k) {
  const stack = [];
  let node = root;
  while (true) {
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    k--;
    if (k === 0) {
      return node.val;
    }
    node = node.right;
  }
}

Go

func kthInBst(
	root *TreeNode, k int,
) int {
	stack := []*TreeNode{}
	node := root
	for {
		for node != nil {
			stack = append(
				stack, node,
			)
			node = node.Left
		}
		last := len(stack) - 1
		node = stack[last]
		stack = stack[:last]
		k--
		if k == 0 {
			return node.Val
		}
		node = node.Right
	}
}

外の繰り返しには終わりの条件を書いていません。k は 1 以上 n 以下なので、全部の節を取り出す前に必ず k が 0 になり、そこで値を返して抜けます。

計算量

時間は O(h + k) です。h は木の高さです。最初に左の端まで h 段下り、そこから k 個取り出すまでに、スタックに積む節と取り出す節がそれぞれ高々 h + k 個です。最も悪い場合は O(n) です
使う記憶は O(h) です。スタックには、根から今の節までの道の上の節しか積まれません。木が片側に伸びきると h は n になり、O(n) です

よくある間違い

数える番号を 1 つずらす。 k は 1 から数えます。0 から数える番号と混ぜると、1 つ隣の値を返します。例 3 のように k が 1 のとき、いちばん小さい値が返るかで確かめます
取り出したあと、右の子へ移り忘れる。取り出した節の右の部分木には、その節の次に小さい値が入っています。右へ移らずに次を取り出すと、右の部分木の値を飛ばします
左の端まで下りきらない。左の子を 1 つだけ積んで止めると、さらに左にある小さい値より先に、大きい値を読んでしまいます。左が無くなるまで積みます
全部読んでから選ぶ。中順に読んで並びに全部入れてから k - 1 番目を返すと、答えは合いますが、k が小さくても全部の節を読み、記憶も O(n) 使います

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

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

スタックの中順の走査で二分探索木の k 番目に小さい値を探す

問題