Trees & Traversals

The shape

A binary tree node has a value and up to two children; almost every tree problem is a traversal plus a little bookkeeping. The whole art is choosing the order and the direction information flows (down into children, or up from them).

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

Depth-first traversals (the three orders)

DFS is recursion; when you visit the node relative to its children defines the order:

def inorder(node, out):
    if not node: return
    inorder(node.left, out)
    out.append(node.val)            # visit between children
    inorder(node.right, out)

• Pre-order (node, L, R) — copy/serialize a tree; the node is processed before its subtrees.
• In-order (L, node, R) — on a BST, yields values in sorted order (the key trick).
• Post-order (L, R, node) — when children must be solved first: height, diameter, deleting a tree, max path sum.

Iterative DFS uses an explicit stack (pre-order pushes right-then-left). In-order iterative pushes lefts, processes, then goes right — worth knowing when recursion depth is a concern.

Morris traversal does in-order in O(1) space by temporarily threading predecessor pointers — the answer to “traverse without recursion or a stack.”

Breadth-first (level order)

A queue visits level by level — for “by level,” “right side view,” “zigzag,” and shortest unweighted distance:

from collections import deque
def level_order(root):
    out, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):           # fix the count → one full level
            node = q.popleft()
            level.append(node.val)
            q.extend(c for c in (node.left, node.right) if c)
        out.append(level)
    return out

The two recursion styles (the core mental model)

Most tree DP is one of these — naming which you’re using clarifies the code:

• Top-down — pass information down as parameters (current depth, path sum, valid range). Good for “does a root-to-leaf path sum to X,” validate-BST bounds.
• Bottom-up (post-order) — each call returns a summary of its subtree, combined at the parent. Good for height, diameter, balanced-check, max-path-sum:

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if not node: return 0
        l, r = height(node.left), height(node.right)
        best = max(best, l + r)          # path through this node
        return 1 + max(l, r)             # height returned upward
    height(root)
    return best

Binary search trees

A BST keeps left < node < right everywhere, so search/insert/delete are O(h) (O(log n) balanced, O(n) degenerate):

• Validate BST — recurse with a (low, high) range; each node must lie strictly inside, and the bounds tighten as you descend. (A common bug: comparing only parent–child, not the full range.)
• In-order = sorted — powers kth smallest (stop at the kth in-order node) and range/closest queries.
• Insert/delete — delete has three cases: leaf (remove), one child (splice), two children (replace with in-order successor, then delete it).
• Lowest common ancestor (BST) — walk down: if both targets are smaller go left, both larger go right, else this node is the LCA. (General-tree LCA: post-order return whether each subtree contains a target.)

Balanced trees (know why they exist)

A BST degrades to O(n) if it grows skewed. Self-balancing trees (AVL, red-black) rotate on insert/delete to keep height O(log n) guaranteed — the basis of ordered maps/sets (std::map, TreeMap). You rarely implement them, but name them when asked “what if the BST is unbalanced?”

Construction and serialization

• Build from traversals — pre-order (or post-order) gives the root; in-order splits left/ right subtrees. Reconstruct recursively.
• Serialize/deserialize — pre-order with explicit nulls (or level-order) encodes a tree to a string and back; a classic “design” question.

Common pitfalls

• Forgetting the null base case in recursion.
• Validate-BST with only local parent comparisons instead of inherited bounds.
• Mutating shared state across recursive calls without nonlocal/return values.
• Deep/skewed trees → recursion depth O(n); mention iterative/Morris if asked.

Choosing in an interview

• “By level” / shortest steps → BFS.
• Aggregate from subtrees (height, diameter, path sum) → post-order bottom-up.
• Carry constraints downward (path sum, valid range) → top-down.
• Sorted order / kth / range on a BST → in-order.
• “Without recursion/stack” → Morris (O(1) space).

Decide order + direction of information first; the code follows almost mechanically.