Binary trees, traversals & BSTs: recursion is just DFS in disguise

A tree is the natural shape for anything recursively defined, and the Python call stack is the depth-first stack you would otherwise manage by hand. Internalise that one mental model and almost every tree problem collapses to a three-line recursion.

What a binary tree is

A binary tree is a hierarchy: one root node, and every node has up to two children (left, right). It is the natural shape for anything recursively defined — file systems, expression parsing, decision trees — and the ordered variant (a BST) gives O(log n) search when balanced.

A tree is its root node. An empty tree is None. Each subtree is itself a tree, which is why almost every tree algorithm is a three-line recursion: do something with the node, recurse left, recurse right.

The recursion-as-DFS mental model — the key insight

Depth-first search means: go as deep as you can down one branch before backing up. Recursion does this for free — each recursive call dives one level deeper, and the call stack remembers where to back up to. So when you write

def f(node):
    if node is None: return        # base case = empty subtree
    ... f(node.left) ... f(node.right) ...

you are doing a DFS, and the Python call stack is the explicit stack you would otherwise manage by hand. The three classic traversals differ only in when you "visit" (process) the node relative to the two recursive calls:

Traversal	Order	Used for
Preorder	visit, left, right (node before children)	copy / serialize
Inorder	left, visit, right (node between children)	sorted output for a BST
Postorder	left, right, visit (node after children)	delete / free, subtree DP

Why inorder of a BST is sorted (memorise this)

The BST invariant: for every node, all values in its left subtree are < node.val, and all values in its right subtree are > node.val. Inorder visits (everything-less) then (node) then (everything-greater) — recursively. By induction that emits values in ascending order. This single fact powers "validate BST", "kth smallest", and "BST → sorted array".

Invariants

Binary tree: each node has ≤ 2 children; no ordering guarantee.
BST: left subtree < node < right subtree, applied at every node — a global range constraint, not just immediate children. This is the classic validate-BST trap.
Height h: a balanced tree has h ≈ log n; a degenerate (linked-list-shaped) tree has h = n.

Complexity

Operation	Time	Space
traversal (any)	O(n)	O(h) recursion / stack depth
BST search / insert	O(h)	O(log n) balanced, O(n) degenerate
BFS level-order	O(n)	O(width) for the queue

The node and a build helper

A tree is its root TreeNode (or None when empty). The build helper consumes a level-order list with None for missing children — the same encoding LeetCode uses, e.g. [3, 9, 20, None, None, 15, 7].

class TreeNode:
    def __init__(self, val: int = 0,
                 left: Optional["TreeNode"] = None,
                 right: Optional["TreeNode"] = None):
        self.val = val
        self.left = left
        self.right = right

def build(values: List[Optional[int]]) -> Optional[TreeNode]:
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    q = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i]); q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i]); q.append(node.right)
        i += 1
    return root

Recursive traversals — identical except for the visit position

Each is O(n) time, O(h) space. Watch how only the placement of out.append(node.val) changes.

def preorder(root: Optional[TreeNode]) -> List[int]:
    out: List[int] = []
    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        out.append(node.val)   # VISIT first
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return out

def inorder(root: Optional[TreeNode]) -> List[int]:
    out: List[int] = []
    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        dfs(node.left)
        out.append(node.val)   # VISIT between children — SORTED for a BST
        dfs(node.right)
    dfs(root)
    return out

def postorder(root: Optional[TreeNode]) -> List[int]:
    out: List[int] = []
    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        dfs(node.left)
        dfs(node.right)
        out.append(node.val)   # VISIT last
    dfs(root)
    return out

Iterative traversals — the hidden stack made explicit

Useful when recursion depth could blow the Python stack, and to prove you understand the control flow. Preorder pushes right before left so left is processed first (the stack is LIFO).

def preorder_iterative(root: Optional[TreeNode]) -> List[int]:
    out: List[int] = []
    if root is None:
        return out
    stack = [root]
    while stack:
        node = stack.pop()
        out.append(node.val)              # visit on pop
        if node.right is not None:
            stack.append(node.right)      # pushed first -> popped last
        if node.left is not None:
            stack.append(node.left)       # pushed last  -> popped first
    return out

Iterative inorder walks left as far as possible pushing nodes; when it cannot go left, it pops (that is the next smallest), visits, then goes right. This mirrors exactly what the recursive version's call stack does.

def inorder_iterative(root: Optional[TreeNode]) -> List[int]:
    out: List[int] = []
    stack: List[TreeNode] = []
    curr = root
    while curr is not None or stack:
        while curr is not None:           # dive left, remembering the path
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()                # leftmost unvisited node
        out.append(curr.val)              # visit
        curr = curr.right                 # now explore its right subtree
    return out

Level-order traversal — BFS (LeetCode 102)

A queue (deque) processes nodes in the order discovered, which for a tree is breadth-first. Snapshot the queue size at the start of each iteration to know exactly how many nodes are on the current level, so output can be grouped by level.

def level_order(root: Optional[TreeNode]) -> List[List[int]]:
    out: List[List[int]] = []
    if root is None:
        return out
    q = deque([root])
    while q:
        level_size = len(q)               # nodes on THIS level
        level: List[int] = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            if node.left is not None:
                q.append(node.left)
            if node.right is not None:
                q.append(node.right)
        out.append(level)
    return out

BFS vs DFS on trees — when to use which

DFS (recursion/stack): "does a root-to-leaf path with property X exist?", subtree aggregates (height, diameter, sum), serialization. Cheap memory, O(h). BFS (queue): anything "by level" — level-order print, min depth, rightmost node per level, shortest #edges from the root. Memory O(width).

Core problems

Maximum depth

A tree's depth is 1 + the deeper of its two subtrees — pure postorder DP, since you need both children's answers before computing yours.

def max_depth(root: Optional[TreeNode]) -> int:
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Same tree

Two trees match iff roots match and left subtrees match and right subtrees match — structural recursion straight off the definition.

def is_same_tree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    return (p.val == q.val
            and is_same_tree(p.left, q.left)
            and is_same_tree(p.right, q.right))

Invert a binary tree

Swap each node's children, recursively. Pre vs post order does not matter, since the swap is local.

def invert(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return None
    root.left, root.right = invert(root.right), invert(root.left)
    return root

Diameter

The longest path (in edges) between any two nodes; the path need not pass through the root. At each node, the longest path through it equals left height + right height (in edges). Compute height bottom-up (postorder) and update a running best as a side effect — one pass, never recomputing heights.

def diameter(root: Optional[TreeNode]) -> int:
    best = 0
    def height(node: Optional[TreeNode]) -> int:
        nonlocal best
        if node is None:
            return 0
        lh = height(node.left)
        rh = height(node.right)
        best = max(best, lh + rh)         # path through this node, in edges
        return 1 + max(lh, rh)            # height of this subtree
    height(root)
    return best

Lowest common ancestor — general binary tree

Recurse. If the current node is p or q, it is a candidate. Search both subtrees. If p and q are found in different subtrees, the current node is their split point — the LCA. If both come back from the same side, propagate that side up.

def lowest_common_ancestor(root: Optional[TreeNode],
                           p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left is not None and right is not None:
        return root                       # split point
    return left if left is not None else right

Lowest common ancestor — BST (faster)

Use the ordering. If both p and q are smaller than the node, the LCA is in the left subtree; if both larger, the right. The moment they straddle the node (or one equals it), that node is the LCA. No need to search both sides — O(h) time, O(1) space.

def lowest_common_ancestor_bst(root: Optional[TreeNode],
                               p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    node = root
    while node is not None:
        if p.val < node.val and q.val < node.val:
            node = node.left
        elif p.val > node.val and q.val > node.val:
            node = node.right
        else:
            return node                   # split point or a match
    return None

Validate a BST — the global-bounds trap (LeetCode 98)

The BST property is global, not local: a node must be greater than everything to its upper-left and less than everything to its lower-right, not just its immediate children. Carry a (low, high) open interval down the recursion; each left move tightens the upper bound to node.val, each right move tightens the lower bound. None means unbounded.

def is_valid_bst(root: Optional[TreeNode]) -> bool:
    def valid(node: Optional[TreeNode],
              low: Optional[int], high: Optional[int]) -> bool:
        if node is None:
            return True
        if low is not None and node.val <= low:
            return False
        if high is not None and node.val >= high:
            return False
        return (valid(node.left, low, node.val) and
                valid(node.right, node.val, high))
    return valid(root, None, None)

Pitfall — checking only immediate children

A tree like TreeNode(5, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))) passes every local "left < parent < right" check yet is not a valid BST: the 4 lives in 5's right subtree but is less than 5. Only the propagated (low, high) bounds catch it.

BST insert and search

Insert walks down using the ordering until it reaches a None slot, then hangs the new leaf there. Search halves the space at each step — binary search expressed on a tree. Both are O(h).

def bst_insert(root: Optional[TreeNode], val: int) -> TreeNode:
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    else:
        root.right = bst_insert(root.right, val)
    return root

def bst_search(root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    node = root
    while node is not None:
        if val == node.val:
            return node
        node = node.left if val < node.val else node.right
    return None

Kth smallest in a BST (LeetCode 230)

Inorder of a BST is sorted, so the kth element visited inorder is the kth smallest. Use the iterative inorder and stop early after k pops — no need to traverse the whole tree. O(h + k) time.

def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    stack: List[TreeNode] = []
    curr = root
    count = 0
    while curr is not None or stack:
        while curr is not None:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        count += 1
        if count == k:
            return curr.val
        curr = curr.right
    raise ValueError("k larger than tree size")

Serialize / deserialize (LeetCode 297)

Serialize with a preorder DFS, emitting a sentinel '#' for None children so the structure is fully recoverable. Preorder works because the root comes first, so deserialization can rebuild top-down in the same order.

def serialize(root: Optional[TreeNode]) -> str:
    parts: List[str] = []
    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:
            parts.append("#")
            return
        parts.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ",".join(parts)

def deserialize(data: str) -> Optional[TreeNode]:
    tokens = iter(data.split(","))
    def build_node() -> Optional[TreeNode]:
        val = next(tokens)
        if val == "#":
            return None
        node = TreeNode(int(val))
        node.left = build_node()          # consume the preorder stream in order
        node.right = build_node()
        return node
    return build_node()

The self-checks confirm the round-trip: serialize(deserialize(s)) == s, and inorder(bst) on a tree built by repeated bst_insert comes back sorted — direct proof of the invariant.

Takeaway

Recursion is DFS, and the three traversals differ only in when you visit. Inorder of a BST is sorted — that one fact drives validate, kth-smallest, and sorted export. The two recurring traps are the global BST bounds (not just immediate children) and choosing BFS only when the problem is genuinely "by level". Next: heaps, when you only ever need the extreme element, fast.