BSTの検証とin-orderの性質
木を伝わるmin/max境界を使い、二分木がBSTかどうかを検証します。また、in-order走査がソート済み列を生成することも確認します。
「BSTの検証とin-orderの性質」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
BSTの検証問題
Validate BST（LeetCode #98）は、多くの候補者がつまずく典型的な面接問題です。単純な方法では、各ノードの値が左の子より大きく、右の子より小さいことだけを確認します。しかし、この局所的なチェックだけでは不十分です。部分木のノードが局所的なルールを満たしていても、BST全体の性質に違反する場合があります。正しい解法では、最小値と最大値の境界を木の下へ伝えていきます。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Why local check fails:
# 5
# / \
# 1 4
# / \
# 3 6
# Node 4's children (3, 6) satisfy local rule,
# but 4 < 5 and is in the RIGHT subtree -- BST violated!
print('Local check is insufficient -- use min/max bounds')最小値・最大値の境界を使う方法
再帰呼び出しに下限と上限を渡します。各ノードで、low < node.val < high を満たすことを確認します。左へ再帰するときは上限を node.val に更新します（左部分木はそれより小さくなければなりません）。右へ再帰するときは下限を node.val に更新します（右部分木はそれより大きくなければなりません）。最初は low = -infinity、high = +infinity とします。
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Valid BST:
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
print(is_valid_bst(valid)) # True
# Invalid BST (3 is in wrong subtree conceptually):
invalid = TreeNode(5)
invalid.left = TreeNode(1)
invalid.right = TreeNode(4)
invalid.right.left = TreeNode(3)
invalid.right.right = TreeNode(6)
print(is_valid_bst(invalid)) # False (4 < 5 in right subtree)中順走査による検証
別の検証方法では、BSTが持つ中順走査でソート順になる性質を利用します。中順走査の結果を集め、それが厳密な昇順になっていることを確認します。この方法は簡潔で、動作も理解しやすいという利点があります。ただし、結果の配列を保存するために O(n) の追加空間が必要です。最適化版では、走査中に単一の prev ポインターを使い、配列全体を保存せずに各隣接要素の組を確認します。
def is_valid_bst_inorder(root):
prev = [float('-inf')]
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if node.val <= prev[0]: # not strictly increasing
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
valid.left.left = TreeNode(1)
valid.left.right = TreeNode(4)
print(is_valid_bst_inorder(valid)) # True
invalid = TreeNode(5)
invalid.left = TreeNode(6) # 6 > 5 in left subtree!
print(is_valid_bst_inorder(invalid)) # False2つの検証方法の比較
最小値・最大値の境界を使う方法は、時間計算量が O(n)、空間計算量が O(h) です（呼び出しスタック上の境界だけを使用します）。中順走査の prev ポインター方式も、時間計算量は O(n)、空間計算量は O(h) です。どちらも最適な方法です。最小値・最大値の方法はより汎用的で、追加の制約がある問題にも自然に拡張できます。面接では両方を説明し、トレードオフを議論できるようにしておきましょう。代替案を理解していることを示せると、強いアピールになります。
# Both approaches:
# Time: O(n) -- visit each node once
# Space: O(h) -- call stack depth
# h = O(log n) balanced, O(n) skewed
# When to choose which:
# min/max bounds:
# - Cleaner for trees with constraints beyond BST
# - No global state (purely functional)
# in-order prev:
# - More intuitive (sorted sequence check)
# - Easier to convert to iterative with a stack
print('Both O(n) time, O(h) space -- choose by clarity')Recover BST：入れ替わった2つのノード
Recover BST（LeetCode #99）は、ちょうど2つのノードが入れ替わったBSTを修復します。中順走査では、正しいBSTからソート済みの列が得られます。2つのノードが入れ替わっている場合、prev.val > current.val となる違反箇所が1つまたは2つ存在します。最初の違反箇所にある最初のノードと、最後の違反箇所にある2番目のノードが、位置の誤った2つのノードです。この2つの値を入れ替えます。
def recover_tree(root):
first = second = prev = None
def inorder(node):
nonlocal first, second, prev
if not node:
return
inorder(node.left)
if prev and prev.val > node.val:
if not first:
first = prev # first violator
second = node # always update second
prev = node
inorder(node.right)
inorder(root)
# Swap values of the two misplaced nodes
if first and second:
first.val, second.val = second.val, first.val
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(2) # 2 and 3 are swapped
recover_tree(root)
print(root.val, root.right.left.val) # 2, 3 (fixed)BSTの中順走査をソート済み配列に変換
BSTをソート済み配列に変換するのは簡単です。中順走査を行い、値を集めるだけです。時間計算量 O(n)、空間計算量 O(n) のこの処理は、ソート済み配列のアルゴリズム（2分探索や2ポインターなど）をBSTのデータに適用する手軽な方法です。「2つのBSTをマージする」や「BSTの中央値を求める」といった、複数の段階からなるBST問題の足がかりになることもよくあります。
def bst_to_sorted_array(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(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print(bst_to_sorted_array(root)) # [1, 2, 3, 4, 5, 6, 7]2つのBSTのマージ
2つのBSTをマージして1つのソート済み配列にするには、それぞれを O(n) と O(m) でソート済み配列に変換し、その後、マージソートのマージ処理を使って2つの配列を O(n+m) で結合します。全体の時間計算量は O(n+m) です。結果をバランスの取れたBSTにする必要がある場合は、結合したソート済み配列をソート済み配列からBSTを作るアルゴリズムに渡します。このように単純な小問題へ分解することが、面接官にも分かりやすい解法の特徴です。
def merge_two_bsts(root1, root2):
def inorder(node, arr):
if not node:
return
inorder(node.left, arr)
arr.append(node.val)
inorder(node.right, arr)
arr1, arr2 = [], []
inorder(root1, arr1)
inorder(root2, arr2)
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
merged.append(arr1[i]); i += 1
else:
merged.append(arr2[j]); j += 1
merged.extend(arr1[i:])
merged.extend(arr2[j:])
return merged
r1 = TreeNode(2); r1.left = TreeNode(1); r1.right = TreeNode(4)
r2 = TreeNode(3); r2.left = TreeNode(0); r2.right = TreeNode(5)
print(merge_two_bsts(r1, r2)) # [0, 1, 2, 3, 4, 5]BSTの範囲内にあるノード数のカウント
値が範囲 [low, high] に含まれるノードの数を数えます。力任せの中順走査では O(n) です。BSTの性質を利用する方法では、不要な部分を枝刈りできます。現在のノードの値が low より小さい場合、左部分木の値もすべて low より小さいため、左部分木を調べる意味はありません。同様に、現在の値が high より大きい場合は右部分木を枝刈りします。平均計算量は O(log n + k) です。ここで k は条件に一致するノード数です。
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 may have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree may 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重複値と厳密なBST・非厳密なBST
標準的なBSTの不変条件では、厳密な不等式を使います。左部分木の値は厳密に小さく、右部分木の値は厳密に大きくなければなりません。問題によっては重複を許し、左部分木に配置する（left <= root）か、右部分木に配置します（root < right）。BSTを検証するときは、必ず問題文で定義されている条件を確認してください。最小値・最大値の境界を使う方法では、境界チェックを厳密にするか等号を含めるかを調整することで、どちらの形式にも対応できます。
# Strict BST (LeetCode default): left < root < right
def is_valid_strict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo < root.val < hi): # STRICT inequalities
return False
return (is_valid_strict(root.left, lo, root.val) and
is_valid_strict(root.right, root.val, hi))
# Non-strict BST (allows duplicates in right): left <= root < right
def is_valid_nonstrict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo <= root.val < hi): # NOTE: <= for left side
return False
return (is_valid_nonstrict(root.left, lo, root.val + 1) and
is_valid_nonstrict(root.right, root.val, hi))
print('Always clarify strict vs non-strict with interviewer')BSTの万能ツールとしての中順走査
中順走査は、BST問題における万能ツールです。ソート順、k番目の要素、範囲クエリ、列の性質などについて問われたら、中順走査（またはその逆）で答えを求められないか検討してください。ほとんどのBST固有の問題は、ソート順に走査し、各ステップで何らかの処理を行うという形に帰着できます。この対応関係をすばやく見抜くことは、面接で重要なスキルです。
# Problems solved elegantly with in-order:
# 1. Validate BST: check prev <= curr during in-order
# 2. Kth smallest: count k steps in in-order
# 3. Kth largest: count k steps in REVERSE in-order
# 4. Closest value to target: find crossover in in-order
# 5. BST to sorted array: collect in-order into list
# 6. Recover BST: find 1-2 violations in in-order
# 7. Sum of range [lo, hi]: accumulate during in-order
# The key insight: in-order visits BST nodes in sorted order.
# All sorted-order reasoning translates to in-order DFS.
print('In-order = sorted access = foundation of BST reasoning')BSTで最も近い値を探す
指定されたターゲットに最も近い値を持つノードを探します。BSTの順序性を利用し、ルートから開始して、それまでに見つけた最も近い値を記録しながらターゲットの方向へ進みます（ターゲットが小さければ左へ、大きければ右へ進みます）。この O(h) の方法は、中順走査より効率的であり、BSTの性質を使って探索範囲を効果的に枝刈りできることを示しています。
def closest_value(root, target):
closest = root.val
curr = root
while curr:
if abs(curr.val - target) < abs(closest - target):
closest = curr.val
if target < curr.val:
curr = curr.left
elif target > curr.val:
curr = curr.right
else:
break # exact match
return closest
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_value(root, 3.714286)) # 4理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、局所的なチェックの落とし穴を避ける最小値・最大値の境界を使ったBST検証、検証に使える中順走査の prev ポインター方式、さらに範囲合計、最近傍値、マージ処理に応用できる、BSTの万能ツールとしての中順走査を学びました。次は、BSTの中順走査の性質を使ってk番目に小さい要素を見つけます。
よくある質問
「BSTの検証とin-orderの性質」レッスンは無料ですか？
はい。「BSTの検証とin-orderの性質」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「BSTの検証とin-orderの性質」で何を学びますか？
木を伝わるmin/max境界を使い、二分木がBSTかどうかを検証します。また、in-order走査がソート済み列を生成することも確認します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「BSTの検証とin-orderの性質」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- BSTへの挿入と探索
- BSTの削除：3つのケース
- BSTの検証とin-orderの性質
- k番目に小さい値、区間和、BSTからソート済み配列へ