BST で k 番目に小さい値
BST で k 番目に小さい値
このレッスンで分かること
- BST の
k番目を聞かれたら、まずin-order = 昇順を思い出す- 計算量は
O(n)時間とO(n)メモリ- もっとも素直なやり方は次の通りです
BST で k 番目に小さい値 とは
BST の in-order 走査が昇順になる性質を使い、k 番目に小さい値を返す関数を実装する。本レッスンでは、BST で k 番目に小さい値 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
前のレッスンで触れた通り、BST を in-order 走査 すると値が昇順に並びます。この性質を使えば、k 番目に小さい値を取り出すのは難しくありません。
本レッスンでは bstKthSmallest(arr, k) を実装します。k は 1 から始まる順位 (1 番目 = 最小値) です。値が存在しない場合 (k が木のノード数を超える、または空木) は -1 を返します。
BST の
k番目を聞かれたら、まずin-order = 昇順を思い出す。これだけで 80% 解けたも同然。
素朴な解法
もっとも素直なやり方は次の通りです。
- BST を
in-orderで走査して、すべての値を配列に詰める k - 1番目のインデックスを返す
計算量は O(n) 時間と O(n) メモリ。実装は簡単で、テストもまず通ります。
Python
def bstKthSmallest(arr, k):
root = buildTree(arr)
out = []
def inorder(node):
if node is None:
return
inorder(node.left)
out.append(node.val)
inorder(node.right)
inorder(root)
if k <= 0 or k > len(out):
return -1
return out[k - 1]早期打ち切り解法
もう少し賢く書くなら、走査中に k 個目を見つけた瞬間に 早期打ち切り します。これで時間計算量は実質 O(h + k) に短縮され、k が小さい場合に有利です。メモリも O(h) まで減らせます。
JavaScript
function bstKthSmallest(arr, k) {
const root = buildTree(arr);
let count = 0;
let answer = -1;
function inorder(node) {
if (node === null || answer !== -1) return;
inorder(node.left);
count++;
if (count === k) {
answer = node.val;
return;
}
inorder(node.right);
}
inorder(root);
return answer;
}クロージャで count と answer を持ち回すパターン。answer !== -1 で 見つけた後はすぐ抜ける ようにしておくと無駄な走査を避けられます。
図でイメージ
図のポイント (テキスト併記)
- この木の in-order は
3, 5, 7, 10, 15, 20
この木の in-order は 3, 5, 7, 10, 15, 20。たとえば k=3 なら 3 番目の 7 を返します。k=6 なら最大値の 20。k=7 以上なら木にそれだけのノードが存在しないので -1。
計算量の整理
| 解法 | 時間 | メモリ | 特徴 |
|---|---|---|---|
| 全走査 + 配列保存 | O(n) | O(n) | 単純で書きやすい |
| 早期打ち切り | O(h + k) | O(h) | k が小さいときに有利 |
実務では木のサイズが大きく k が小さい時 (例: k = 1 で最小値が欲しい)、早期打ち切り版が選ばれます。本問では正解できればどちらでも OK です。
木の高さを
hとすると、再帰のスタックは最大O(h)。平衡 BST ならh = log n。
Python での実装例
Python
def bstKthSmallest(arr, k):
root = buildTree(arr)
state = {'count': 0, 'answer': -1}
def inorder(node):
if node is None or state['answer'] != -1:
return
inorder(node.left)
state['count'] += 1
if state['count'] == k:
state['answer'] = node.val
return
inorder(node.right)
inorder(root)
return state['answer']Python でクロージャの値を書き換えるには nonlocal か 辞書 を使うのが定番。本サンプルでは state 辞書で持ち回しています。
よくある間違い
第 1 に、k が 1 始まり か 0 始まり かの混同。本問は 1 始まりです。第 2 に、in-order の代わりに pre-order や post-order を間違って使うこと。pre-order は親 → 左 → 右、post-order は左 → 右 → 親で、どちらも昇順にはなりません。第 3 に、不正な k (0 以下や木のサイズ超え) のときに -1 を返し忘れること。
同じ問題で
k 番目に大きい値を聞かれることもある。その場合は逆順 in-order (右 → 親 → 左) で走査するか、n - k + 1番目を取れば良い。
やってみよう
[10, 5, 15, 3, 7, null, 20]でk=1→3、k=4→10、k=6→20を確認するk=0やk=7で-1が返ることを確認する- 早期打ち切りの動きを
console.logを仕込んで観察してみる
よくある質問
Q. BST はなぜ高速ですか？
A. 平衡している場合、検索・挿入・削除がいずれも O(log n) です。各ノードで「左<自分<右」を満たすため、半分ずつ探索範囲が絞れます。ただし偏ると O(n) に劣化するため、実用では赤黒木・AVL 木のような自動平衡化された実装を使います。
Q. in-order 走査で何が得られますか？
A. BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。
Q. BST に重複値を入れるとどうなりますか？
A. 実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap<Key, Integer> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は BST から値を削除する で、ノードを削除しても BST の性質を保つための削除アルゴリズム（葉・子1つ・子2つの3ケース）を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- BST kth smallest の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. BST kth smallest とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- in-order 走査が昇順になる BST の性質を利用する
kは 1 始まりの順位。1 番目 = 最小値kが範囲外、または空木の場合は-1を返す
入出力例
test-cases.txt
bstKthSmallest([], 1) → -1
bstKthSmallest([10], 1) → 10
bstKthSmallest([10], 2) → -1
bstKthSmallest([10,5,15,3,7,null,20], 1) → 3
bstKthSmallest([10,5,15,3,7,null,20], 4) → 10
bstKthSmallest([10,5,15,3,7,null,20], 6) → 20
bstKthSmallest([10,5,15,3,7,null,20], 0) → -1