k番目に小さい値、区間和、BSTからソート済み配列へ
ソート済みのin-order走査を活用し、k番目に小さい要素をO(k)で見つけ、範囲内の値の合計をO(log n + k)で求めます。
「k番目に小さい値、区間和、BSTからソート済み配列へ」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
BSTでk番目に小さい要素
Kth Smallest Element in a BST（LeetCode #230）は、ソート順になる中順走査を直接活用する典型的な問題です。中順走査ではノードが昇順に訪問されるため、走査しながらノード数を数え、カウントが k になったときの値を返します。時間計算量は O(h + k) です。ここで h は木の高さ（左端のノードに到達するまでのコスト）、k は中順走査で進むステップ数です。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def kth_smallest(root, k):
count = [0]
result = [None]
def inorder(node):
if not node or result[0] is not None:
return
inorder(node.left)
count[0] += 1
if count[0] == k:
result[0] = node.val
return
inorder(node.right)
inorder(root)
return result[0]
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1)) # 1
print(kth_smallest(root, 2)) # 2k番目に小さい要素：スタックを使った反復処理
反復版では、明示的なスタックを使う中順走査のパターンを利用します。null に到達するまで左のノードを積み、その後、取り出してカウントします。カウントが k に達したら、現在のノードの値を返します。これにより、非常に深い木でPythonの再帰制限に達することを避けられます。時間計算量は同じく O(h + k)、空間計算量は O(h) です。面接では、再帰版の後に反復版を求められることがよくあります。
def kth_smallest_iterative(root, k):
stack = []
curr = root
count = 0
while curr or stack:
while curr: # go as far left as possible
stack.append(curr)
curr = curr.left
curr = stack.pop() # process node
count += 1
if count == k:
return curr.val
curr = curr.right # move to right subtree
return -1 # k out of range
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3)) # 3BSTでk番目に大きい要素
Kth Largestでは、逆中順走査（右 → ルート → 左）を使い、ノードを降順に訪問します。k個分進むまで数え、現在のノードの値を返します。これはk番目に小さい要素を求める処理と対称で、時間計算量は O(h + k) です。木のサイズが分かっている場合は、kth_smallest(root, total_count - k + 1) を計算する方法もありますが、逆中順走査の方がより洗練されています。
def kth_largest(root, k):
count = [0]
result = [None]
def reverse_inorder(node):
if not node or result[0] is not None:
return
reverse_inorder(node.right) # visit LARGER values first
count[0] += 1
if count[0] == k:
result[0] = node.val
return
reverse_inorder(node.left)
reverse_inorder(root)
return result[0]
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_largest(root, 1)) # 4 (largest)
print(kth_largest(root, 2)) # 3 (2nd largest)BSTの範囲合計
Range Sum of BST（LeetCode #938）では、[low, high] に含まれるすべての値の合計を求めます。BSTの性質を利用して枝刈りします。現在のノードの値が low より小さい場合、左部分木全体も low 未満なので、左部分木を飛ばします。現在の値が high より大きい場合は、右部分木を飛ばします。これにより多くの枝を省略でき、完全な中順走査より効率的です。
def range_sum_bst(root, low, high):
if not root:
return 0
total = 0
if low <= root.val <= high:
total += root.val
if root.val > low: # left subtree might have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree might have values <= high
total += range_sum_bst(root.right, low, high)
return total
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15)) # 7+10+15 = 32範囲内にあるノード数のカウント
[low, high] の範囲内にあるノード数も、同じ枝刈りのロジックで数えられます。別の方法として、中順走査で得た配列に対して bisect_left/bisect_right を使うこともできます。しかし、BSTを直接走査する方法は O(log n + k) であるのに対し、先に配列へ変換すると常に O(n) かかります。多数の範囲クエリに答える必要がある場合は、部分木のノード数を保持する拡張BSTを構築すればクエリごとに O(log n) で処理できるため、それ以外では直接走査を選びましょう。
def count_range(root, low, high):
if not root:
return 0
count = 0
if low <= root.val <= high:
count += 1
if root.val > low:
count += count_range(root.left, low, high)
if root.val < high:
count += count_range(root.right, low, high)
return count
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(count_range(root, 6, 15)) # 7, 10, 15 = 3BSTをソート済み配列に変換（完全なアルゴリズム）
BSTをソート済み配列に変換する処理は、時間計算量 O(n)、空間計算量 O(n) です。中順走査を行い、各値を追加します。これは、「2つのBSTをマージする」、「BSTの中央値を求める」、「2つのBSTが同じ中順走査列を持つか確認する」といった複数段階の問題の出発点になります。生成された配列ではインデックスによる O(1) のアクセス、2分探索、2ポインターの手法を利用できますが、これらはBSTそのものでは直接利用できません。
def bst_to_sorted(root):
result = []
def inorder(node):
if not node:
return
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(bst_to_sorted(root)) # [1, 3, 4, 5, 6, 8, 9]
# Binary search on the resulting sorted array:
import bisect
arr = bst_to_sorted(root)
print(bisect.bisect_left(arr, 6)) # 4 (index of 6)拡張 BST：部分木のサイズ
拡張 BST は各ノードに、その部分木のサイズなどの追加情報を格納します。部分木のサイズがあれば、k 番目に小さい要素を O(log n) で求められます。各ノードで、左部分木のサイズが k-1 なら現在のノードが答えです。左部分木のサイズが k 以上なら左へ再帰し、それ以外は k から差し引いて右へ再帰します。これは競技プログラミングで使われる順序統計木の基盤となるデータ構造です。
class AugNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.size = 1 # subtree size
def get_size(node):
return node.size if node else 0
def update_size(node):
if node:
node.size = 1 + get_size(node.left) + get_size(node.right)
def kth_smallest_aug(root, k):
left_size = get_size(root.left)
if k == left_size + 1:
return root.val # current node is kth
elif k <= left_size:
return kth_smallest_aug(root.left, k)
else:
return kth_smallest_aug(root.right, k - left_size - 1)
print('Augmented BST: O(log n) kth smallest with subtree sizes')BST で 2 つのノードの間にあるすべての値を検索する
2 つのノード p と q の間（p.val < q.val）にあるすべての値を返すには、中順走査と範囲の枝刈りを組み合わせます。p.val を通過したら値の収集を開始し、q.val を過ぎたら停止します。これは区間和を一般化したもので、2 つの検索値の間にあるソート済みの列を O(h + k) 時間で取得できます。
def values_between(root, low, high):
result = []
def inorder(node):
if not node:
return
if node.val > low: # might be values > low on left
inorder(node.left)
if low < node.val < high: # strictly between
result.append(node.val)
if node.val < high: # might be values < high on right
inorder(node.right)
inorder(root)
return result
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
print(values_between(root, 6, 15)) # [7, 10, 12]BST の中央値
BST の中央値 は、中順走査で得られる列の中央の値です。n 個のノードがある場合、中央値は n // 2（0 始まり）の位置にあります。ソート済みの配列全体を収集してその位置の要素を取得する方法と、まず n 個のノードを数え、次に n // 2 番目のノードで停止する 2 回目の中順走査を行う方法があります。また、k = n // 2 + 1 として k 番目に小さい要素を求める方法もあります。
def count_nodes(root):
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
def median_of_bst(root):
n = count_nodes(root)
if n == 0:
return None
k = n // 2 + 1 # (n+1)/2-th element for odd, n/2+1-th for even
return kth_smallest(root, k)
def kth_smallest(root, k):
count = [0]; result = [None]
def inorder(node):
if not node or result[0] is not None: return
inorder(node.left)
count[0] += 1
if count[0] == k: result[0] = node.val; return
inorder(node.right)
inorder(root); return result[0]
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
print(median_of_bst(root)) # 4 (middle of [1,3,4,5,8])対象値に最も近い k 個の値
BST から対象値に最も近い k 個の値を見つけます。2 ポインターアプローチでは、まずソート済み配列に変換し、サイズ k のスライディングウィンドウを使います。別の方法として、サイズ k の max-heap を使い、距離を追加して、サイズが k を超えたら取り出します。ソート済み配列を使う方法は O(n) 時間で単純です。一方、ヒープを使う方法は O(n log k) ですが、ストリーミングコンテキストで利用できます。
import heapq
def closest_k_values(root, target, k):
# Collect sorted values
arr = []
def inorder(node):
if not node: return
inorder(node.left)
arr.append(node.val)
inorder(node.right)
inorder(root)
# Two-pointer sliding window of size k
left, right = 0, k - 1
while right < len(arr) - 1:
if abs(arr[left] - target) <= abs(arr[right + 1] - target):
break # left is closer, don't advance
left += 1
right += 1
return arr[left:right + 1]
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_k_values(root, 3.7, 2)) # [3, 4]後続要素の順序特性の活用
多くの BST 問題は、ソート順における次または前の要素を見つける問題に帰着できます。これは BST のナビゲーションを使えば O(log n) で実行できます。先ほど構築したイテレータを使えば、next を償却 O(1) で実行できます。k 番目に小さい要素、区間和、最近傍値に関する知識を組み合わせると、「中順走査のソート順を利用すると、この処理はどのように単純化できるか」と考えることで、ほとんどの BST 面接問題を解けます。このメタパターンが、BST の問題解決における指針となります。
# Meta-pattern for BST problems:
# Step 1: What sorted-order property does this exploit?
# Step 2: Is in-order (ascending) or reverse in-order (descending) needed?
# Step 3: Can I prune using BST ordering to avoid O(n) scan?
# Quick reference:
# kth smallest -> in-order, stop at kth node
# kth largest -> reverse in-order, stop at kth node
# range sum -> in-order + BST pruning
# closest value -> walk toward target, track best
# median -> kth with k = n//2+1
# sorted array -> full in-order
# validate -> in-order prev check or min/max bounds
print('Sorted in-order is the universal BST problem tool')理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、O(h+k) の中順走査と逆中順走査を使ったk 番目に小さい要素と大きい要素、効率的な範囲検索を実現するBST の枝刈りを使った区間和、そして配列ベースのアルゴリズムの基盤となる BST からソート済み配列への変換について学びました。次はヒープと優先度付きキューを扱います。
よくある質問
「k番目に小さい値、区間和、BSTからソート済み配列へ」レッスンは無料ですか？
はい。「k番目に小さい値、区間和、BSTからソート済み配列へ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「k番目に小さい値、区間和、BSTからソート済み配列へ」で何を学びますか？
ソート済みのin-order走査を活用し、k番目に小さい要素をO(k)で見つけ、範囲内の値の合計をO(log n + k)で求めます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「k番目に小さい値、区間和、BSTからソート済み配列へ」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- BSTへの挿入と探索
- BSTの削除：3つのケース
- BSTの検証とin-orderの性質
- k番目に小さい値、区間和、BSTからソート済み配列へ