Trees & Binary Search Trees

A tree is a connected acyclic graph. Binary tree: each node has at most 2 children (left, right).

Tree traversals — memorize all four:
• Inorder   (Left → Root → Right) → gives sorted order for BST
• Preorder  (Root → Left → Right) → useful for copying/serializing tree
• Postorder (Left → Right → Root) → useful for deleting/evaluating tree
• Level-order (BFS) → process level by level

BST property: left subtree < node < right subtree. This gives O(log n) search, insert, delete for balanced trees. O(n) worst case for skewed trees.

The key insight for tree problems: most tree problems have a recursive structure. Ask: "what does this function return for a leaf node? What does it return for a null node? Can I combine results from left and right subtree?"

DFS on trees is almost always recursive. The base case is always: if not node: return something.

1from collections import deque
2
3class TreeNode:
4    def __init__(self, val=0, left=None, right=None):
5        self.val   = val
6        self.left  = left
7        self.right = right
8
9def make_tree():
10    #      4
11    #     /     #    2   6
12    #   /  /     #  1  3 5  7
13    root = TreeNode(4)
14    root.left  = TreeNode(2, TreeNode(1), TreeNode(3))
15    root.right = TreeNode(6, TreeNode(5), TreeNode(7))
16    return root
17
18# ── Four traversals ───────────────────────────────────────────────
19def inorder(node):
20    if not node: return []
21    return inorder(node.left) + [node.val] + inorder(node.right)
22
23def preorder(node):
24    if not node: return []
25    return [node.val] + preorder(node.left) + preorder(node.right)
26
27def level_order(root):
28    if not root: return []
29    result, queue = [], deque([root])
30    while queue:
31        level = []
32        for _ in range(len(queue)):
33            node = queue.popleft()
34            level.append(node.val)
35            if node.left:  queue.append(node.left)
36            if node.right: queue.append(node.right)
37        result.append(level)
38    return result
39
40# ── Max Depth ────────────────────────────────────────────────────
41def max_depth(node) -> int:
42    if not node: return 0
43    return 1 + max(max_depth(node.left), max_depth(node.right))
44
45# ── Is Balanced? ─────────────────────────────────────────────────
46def is_balanced(node) -> bool:
47    def height(node):
48        if not node: return 0
49        lh = height(node.left)
50        rh = height(node.right)
51        if lh == -1 or rh == -1 or abs(lh - rh) > 1:
52            return -1          # -1 signals unbalanced subtree
53        return 1 + max(lh, rh)
54    return height(node) != -1
55
56# ── Lowest Common Ancestor ────────────────────────────────────────
57def lca(root, p, q):
58    if not root or root == p or root == q:
59        return root
60    left  = lca(root.left, p, q)
61    right = lca(root.right, p, q)
62    if left and right: return root    # p and q on different sides
63    return left or right
64
65# ── Validate BST ─────────────────────────────────────────────────
66def is_valid_bst(node, min_val=float('-inf'), max_val=float('inf')) -> bool:
67    if not node: return True
68    if not (min_val < node.val < max_val): return False
69    return (is_valid_bst(node.left,  min_val, node.val) and
70            is_valid_bst(node.right, node.val, max_val))
71
72root = make_tree()
73print(inorder(root))         # [1, 2, 3, 4, 5, 6, 7]
74print(level_order(root))     # [[4], [2,6], [1,3,5,7]]
75print(max_depth(root))       # 3
76print(is_balanced(root))     # True
77print(is_valid_bst(root))    # True