Chapter 5: Binary Trees and Binary Search Trees

Vol 2: Algorithm Forest Adventure · Station 5

---

Metadata Card

Attribute	Value
Prerequisites	Arrays and Linked Lists (Chapter 2), Recursion (Chapter 12 preview)
Difficulty	(Core)
Keywords	Binary Tree BST Inorder Preorder Postorder Level Order Backtracking

---

Your Progress

The forest paths start branching — at every intersection there are two directions (left and right), and all left paths lead to smaller numbers while all right paths lead to larger ones. This isn't a coincidence — this is the fallen leaves of a Binary Search Tree.

---

Breakthrough · Origins

The Node: val / left / right

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

BST Core Rule

For any node: all nodes in its left subtree ≤ node < all nodes in its right subtree

BST Search

def search_recursive(node, target):
    if node is None or node.val == target:
        return node
    if target < node.val:
        return search_recursive(node.left, target)
    return search_recursive(node.right, target)

def search_iterative(root, target):
    cur = root
    while cur and cur.val != target:
        cur = cur.left if target < cur.val else cur.right
    return cur

BST Insert

def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root

BST Delete (Three Cases)

def delete(root, val):
    if root is None:
        return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        # Case 1 & 2: 0 or 1 child
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        # Case 3: Two children — find inorder successor
        succ = _find_min(root.right)
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

def _find_min(node):
    while node.left:
        node = node.left
    return node

Four Traversals

def preorder(node, result=None):   # Root → Left → Right
    if result is None: result = []
    if node:
        result.append(node.val)
        preorder(node.left, result)
        preorder(node.right, result)
    return result

def inorder(node, result=None):     # Left → Root → Right
    if result is None: result = []
    if node:
        inorder(node.left, result)
        result.append(node.val)
        inorder(node.right, result)
    return result

def postorder(node, result=None):   # Left → Right → Root
    if result is None: result = []
    if node:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.val)
    return result

def level_order(root):
    from collections import deque
    if not root: return []
    result, q = [], deque([root])
    while q:
        node = q.popleft()
        result.append(node.val)
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)
    return result

BST Degradation

Inserting [1, 2, 3, 4, 5] sequentially creates a chain (linked list), O(n) search. This is why balanced trees (Chapter 6) exist.

---

Verification Checklist

• [ ] Can explain BST core rule: left ≤ node < right
• [ ] Can hand-write BST insert (recursive + iterative)
• [ ] Can hand-write BST delete (three cases)
• [ ] Can write all four traversals
• [ ] Can explain BST's fatal weakness — degradation into a linked list

---

Traveler's Notes

• BST's inorder traversal = sorted sequence. This equivalence is the foundation of all tree-based sorting.
• Recursion makes tree code elegant. Don't trace it — trust it.
• The BST node structure (val, left, right) is the template for all advanced trees.

---

→ Next Stop Preview

Chapter 6: Balanced Trees and Red-Black Trees — "When BST degrades, balance it!"