The runnable files used in this lesson. Copy them into your own project and experiment.
src/01_bst_insert_search.py Python #Topic: BST Insertion, Search, In-order Traversal
#Time: O(log n) average, O(n) worst (skewed tree)
#Space: O(n) storage, O(h) recursion stack
from __future__ import annotations
class BSTNode:
"""Binary search tree node."""
def __init__(self, val: int) -> None:
self.val = val
self.left: BSTNode | None = None
self.right: BSTNode | None = None
def __repr__(self) -> str:
return f"BSTNode({self.val})"
class BST:
"""Binary search tree implementation."""
def __init__(self) -> None:
self.root: BSTNode | None = None
def insert(self, val: int) -> None:
"""Insert value.
Time: O(h) — h = tree height
Space: O(h) — recursive stack"""
self.root = self._insert(self.root, val)
def _insert(self, node: BSTNode | None, val: int) -> BSTNode:
if node is None:
return BSTNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
#val == node.val: Ignore duplicates
return node
def search(self, val: int) -> bool:
"""Search value.
Time: O(h)
Space: O(1) — iterative"""
return self._search_iterative(self.root, val)
def _search_iterative(self, root: BSTNode | None, val: int) -> bool:
curr = root
while curr:
if val == curr.val:
return True
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return False
def search_node(self, val: int) -> BSTNode | None:
"""Return the node itself (None if not found).
Time: O(h)
Space: O(1)"""
curr = self.root
while curr:
if val == curr.val:
return curr
curr = curr.left if val < curr.val else curr.right
return None
def inorder(self) -> list[int]:
"""In-order traversal — always in sorted order.
Time: O(n)
Space: O(n) result + O(h) stack"""
result: list[int] = []
self._inorder(self.root, result)
return result
def _inorder(self, node: BSTNode | None, result: list[int]) -> None:
if node is None:
return
self._inorder(node.left, result)
result.append(node.val)
self._inorder(node.right, result)
def minimum(self) -> int | None:
"""Minimum value (leftmost node).
Time: O(h)
Space: O(1)"""
if self.root is None:
return None
curr = self.root
while curr.left:
curr = curr.left
return curr.val
def maximum(self) -> int | None:
"""Maximum value (rightmost node).
Time: O(h)
Space: O(1)"""
if self.root is None:
return None
curr = self.root
while curr.right:
curr = curr.right
return curr.val
def height(self) -> int:
"""Tree height.
Time: O(n)
Space: O(h)"""
return self._height(self.root)
def _height(self, node: BSTNode | None) -> int:
if node is None:
return -1
return 1 + max(self._height(node.left), self._height(node.right))
#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
bst = BST()
values = [8, 3, 10, 1, 6, 14, 4, 7, 13]
print("=== Insertion ===")
for v in values:
bst.insert(v)
print(f" insert({v})")
print("=== In-order Traversal (Sorted Result) ===")
print(f" {bst.inorder()}")
print("=== Search ===")
for v in [6, 13, 99]:
found = bst.search(v)
print(f" search({v:2d}) → {found}")
print("=== Minimum / Maximum ===")
print(f"Minimum: {bst.minimum()}")
print(f"Maximum: {bst.maximum()}")
print(f"Tree Height: {bst.height()}")
#Insertion in sorted order → skewed tree
print("=== Skewed Tree (Insertion in Sorted Order) ===")
skewed = BST()
for v in [1, 2, 3, 4, 5]:
skewed.insert(v)
print(f"Height: {skewed.height()} (Skewed: n-1 = {5-1})")
print(f"In-order: {skewed.inorder()}")src/02_bst_delete.py Python #Topic: BST Deletion — Leaf, One Child, Two Children (Successor)
#Time: O(h) — h = tree height (average O(log n), worst O(n))
#Space: O(h) — recursive stack
from __future__ import annotations
class BSTNode:
def __init__(self, val: int) -> None:
self.val = val
self.left: BSTNode | None = None
self.right: BSTNode | None = None
class BST:
def __init__(self) -> None:
self.root: BSTNode | None = None
#── Insertion (same as previous lecture) ────────────────────────────────────────────
def insert(self, val: int) -> None:
self.root = self._insert(self.root, val)
def _insert(self, node: BSTNode | None, val: int) -> BSTNode:
if node is None:
return BSTNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
return node
#── Deletion ──────────────────────────────────────────────────────────────
def delete(self, val: int) -> None:
"""Delete a value from a BST.
3 cases:
1) Leaf: just remove
2) One child: replace with the child
3) Two children: replace with successor (smallest value in the right subtree)
Time: O(h)
Space: O(h)"""
self.root = self._delete(self.root, val)
def _delete(self, node: BSTNode | None, val: int) -> BSTNode | None:
if node is None:
return None #No value
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
#Target node for deletion found
if node.left is None:
#Case 1 & 2a: No left child → replace with right (including leaf)
return node.right
elif node.right is None:
#Case 2b: No right child → replace with left
return node.left
else:
#Case 3: Two children → replace with successor (minimum of right subtree)
successor_val = self._find_min(node.right)
node.val = successor_val
#Delete successor node from right subtree
node.right = self._delete(node.right, successor_val)
return node
def _find_min(self, node: BSTNode) -> int:
"""Minimum value of a subtree (leftmost).
Time: O(h)
Space: O(1)"""
curr = node
while curr.left:
curr = curr.left
return curr.val
def _find_max(self, node: BSTNode) -> int:
"""Maximum value of a subtree (rightmost).
Time: O(h)
Space: O(1)"""
curr = node
while curr.right:
curr = curr.right
return curr.val
def inorder(self) -> list[int]:
result: list[int] = []
self._inorder(self.root, result)
return result
def _inorder(self, node: BSTNode | None, result: list[int]) -> None:
if node is None:
return
self._inorder(node.left, result)
result.append(node.val)
self._inorder(node.right, result)
#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
def make_bst(values: list[int]) -> BST:
bst = BST()
for v in values:
bst.insert(v)
return bst
print("=== Case 1: Delete Leaf Node ===")
# 8
# / \
# 3 10
# / \
# 1 6
bst = make_bst([8, 3, 10, 1, 6])
print(f"Before deletion: {bst.inorder()}")
bst.delete(1) #Leaf deletion
print(f"delete(1): {bst.inorder()}")
bst.delete(6) #Leaf deletion
print(f"delete(6): {bst.inorder()}")
print("=== Case 2: Delete Node with One Child ===")
# 8
# / \
# 3 10
# \
# 14
bst2 = make_bst([8, 3, 10, 14])
print(f"Before deletion: {bst2.inorder()}")
bst2.delete(10) #Node with only right child
print(f"delete(10): {bst2.inorder()}")
print("=== Case 3: Delete Node with Two Children ===")
# 8
# / \
# 3 10
# / \ \
# 1 6 14
# / \ /
# 4 7 13
bst3 = make_bst([8, 3, 10, 1, 6, 14, 4, 7, 13])
print(f"Before deletion: {bst3.inorder()}")
bst3.delete(3) #Two children (successor = 4)
print(f"delete(3): {bst3.inorder()}")
bst3.delete(8) #Root deletion (successor = 10)
print(f"delete(8): {bst3.inorder()}")
print("=== Deleting Non-existent Value (Should Not Cause Error) ===")
bst3.delete(999)
print(f"delete(999): {bst3.inorder()}")src/03_bst_validate.py Python #Topic: BST Validation, k-th Smallest Element
#Time: O(n) — both validation/k-th
#Space: O(h) — recursive stack
from __future__ import annotations
import math
class BSTNode:
def __init__(self, val: int,
left: "BSTNode | None" = None,
right: "BSTNode | None" = None) -> None:
self.val = val
self.left = left
self.right = right
def is_valid_bst(root: BSTNode | None) -> bool:
"""BST Validity Check.
Key: Simply checking left.val < node.val < right.val is wrong!
Each node must be within the range [min_bound, max_bound].
Example: The below is locally correct but violates BST:
5
/ \
1 4
/ \
3 6
(The right 6 of 4 is greater than root 5, so it violates)
Time: O(n)
Space: O(h)"""
def validate(
node: BSTNode | None,
min_val: float,
max_val: float,
) -> bool:
if node is None:
return True
if not (min_val < node.val < max_val):
return False
return (
validate(node.left, min_val, node.val)
and validate(node.right, node.val, max_val)
)
return validate(root, -math.inf, math.inf)
def kth_smallest(root: BSTNode | None, k: int) -> int:
"""k-th Smallest (1-indexed).
Since in-order traversal (left→current→right) is ascending, the k-th visited node is the answer.
Time: O(h + k) — Best case O(log n), Worst case O(n)
Space: O(h)"""
count = 0
result = -1
def inorder(node: BSTNode | None) -> None:
nonlocal count, result
if node is None or count >= k:
return
inorder(node.left)
count += 1
if count == k:
result = node.val
return
inorder(node.right)
inorder(root)
return result
def kth_smallest_iterative(root: BSTNode | None, k: int) -> int:
"""k-th Smallest — Iterative (Stack) Method.
Time: O(h + k)
Space: O(h)"""
stack: list[BSTNode] = []
curr: BSTNode | None = root
count = 0
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
count += 1
if count == k:
return curr.val
curr = curr.right
return -1 #k > number of nodes
def inorder_successor(root: BSTNode | None, target: int) -> int | None:
"""In-order Successor (smallest value greater than target).
Time: O(h)
Space: O(1)"""
successor: int | None = None
curr = root
while curr:
if target < curr.val:
successor = curr.val #Update candidate
curr = curr.left
else:
curr = curr.right #If ≥ target, go right
return successor
#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
#Valid BST
# 5
# / \
# 3 7
# / \ / \
# 1 4 6 8
valid_root = BSTNode(5,
BSTNode(3, BSTNode(1), BSTNode(4)),
BSTNode(7, BSTNode(6), BSTNode(8))
)
#Invalid BST (3's right is 4, but under root 5's left, 4 > 3 but < 5 OK,
#The example below is a clear violation)
# 5
# / \
# 1 4
# / \
# 3 6
invalid_root = BSTNode(5,
BSTNode(1),
BSTNode(4, BSTNode(3), BSTNode(6))
)
print("=== BST Validation ===")
print(f"Valid BST: {is_valid_bst(valid_root)}") # True
print(f"Invalid BST: {is_valid_bst(invalid_root)}") # False
print("\n=== k-th Smallest Element ===")
for k in range(1, 8):
val_r = kth_smallest(valid_root, k)
val_i = kth_smallest_iterative(valid_root, k)
print(f"k={k}: Recursive={val_r}, Iterative={val_i}")
print("\n=== Inorder Successor ===")
for target in [3, 5, 7, 8]:
succ = inorder_successor(valid_root, target)
print(f"Successor of {target}: {succ}")src/04_bst_applications.py Python #Topic: BST Applications — Sorting, Range Query, Floor/Ceil
#Time: O(n log n) BST Sort, O(log n + k) Range Query
# Space: O(n)
from __future__ import annotations
class BSTNode:
def __init__(self, val: int) -> None:
self.val = val
self.left: BSTNode | None = None
self.right: BSTNode | None = None
class BST:
def __init__(self) -> None:
self.root: BSTNode | None = None
def insert(self, val: int) -> None:
self.root = self._insert(self.root, val)
def _insert(self, node: BSTNode | None, val: int) -> BSTNode:
if node is None:
return BSTNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
return node
def inorder(self) -> list[int]:
"""In-order traversal = sorted array.
Time: O(n)
Space: O(n)"""
result: list[int] = []
self._inorder(self.root, result)
return result
def _inorder(self, node: BSTNode | None, result: list[int]) -> None:
if node is None:
return
self._inorder(node.left, result)
result.append(node.val)
self._inorder(node.right, result)
def range_query(self, low: int, high: int) -> list[int]:
"""Return all values within the [low, high] range.
Key: If the current value is greater than low, search left; if less than high, search right
Time: O(log n + k) — k = number of results
Space: O(k + h)"""
result: list[int] = []
self._range_query(self.root, low, high, result)
return result
def _range_query(
self,
node: BSTNode | None,
low: int,
high: int,
result: list[int],
) -> None:
if node is None:
return
if node.val > low:
self._range_query(node.left, low, high, result)
if low <= node.val <= high:
result.append(node.val)
if node.val < high:
self._range_query(node.right, low, high, result)
def floor(self, val: int) -> int | None:
"""floor(val): the largest value less than or equal to val.
Time: O(h)
Space: O(1)"""
result: int | None = None
curr = self.root
while curr:
if curr.val == val:
return curr.val
elif curr.val < val:
result = curr.val #Candidate
curr = curr.right
else:
curr = curr.left
return result
def ceil(self, val: int) -> int | None:
"""ceil(val): the smallest value greater than or equal to val.
Time: O(h)
Space: O(1)"""
result: int | None = None
curr = self.root
while curr:
if curr.val == val:
return curr.val
elif curr.val > val:
result = curr.val #Candidate
curr = curr.left
else:
curr = curr.right
return result
def count_range(self, low: int, high: int) -> int:
"""Number of nodes within the [low, high] range (using BST).
Time: O(log n + k)
Space: O(h)"""
return len(self.range_query(low, high))
def bst_sort(arr: list[int]) -> list[int]:
"""Sorting using BST.
Time: O(n log n) on average, O(n²) worst case (skewed tree)
Space: O(n)
Note: If the array is already sorted, O(n²) — practically, heapq/sorted() is preferred"""
bst = BST()
for v in arr:
bst.insert(v)
return bst.inorder()
#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
values = [20, 8, 22, 4, 12, 10, 14]
bst = BST()
for v in values:
bst.insert(v)
print("=== BST Sort ===")
print(f"Input: {values}")
print(f"Sorted: {bst.inorder()}")
print("\n=== Range Query [10, 20] ===")
print(f"Result: {bst.range_query(10, 20)}")
print("\n=== Floor / Ceil ===")
test_vals = [5, 9, 11, 13, 21, 23]
print(f"{'Value':>5} | {'floor':>8} | {'ceil':>8}")
print("-" * 28)
for v in test_vals:
f = bst.floor(v)
c = bst.ceil(v)
print(f"{v:>5} | {str(f):>8} | {str(c):>8}")
print("\n=== BST Sort (Random Array) ===")
import random
arr = random.sample(range(1, 101), 10)
print(f"Input: {arr}")
print(f"Sorted: {bst_sort(arr)}")
print("\n=== Count Within Range ===")
print(f"Number of nodes in [10, 20]: {bst.count_range(10, 20)}")
print(f"Number of nodes in [1, 5]: {bst.count_range(1, 5)}")