Trees

Trees are hierarchical structures. Many problems are naturally recursive and revolve around how information flows through the tree.

1. Traversals (The "Vocabulary")

Before solving tree problems, you must be comfortable with the standard traversals. Each visits nodes in a different order:

• Preorder (DFS): Root -> Left -> Right. Used for copying trees or prefix expressions.
• Inorder (DFS): Left -> Root -> Right. Crucial for BSTs (yields sorted order).
• Postorder (DFS): Left -> Right -> Root. Used for deleting trees or aggregating info from children (e.g., height).
• Level-Order (BFS): Row by row. Used for finding shortest paths in unweighted graphs.

2. Thinking Recursively: The Information Flow

Most tree problems boil down to one question: What information needs to flow where?

1. Down the tree (Parameters): Pass values from parent to child.
   • Examples: current_depth, max_value_so_far, target_sum_remaining.
2. Up the tree (Return Values): Pass values from child to parent.
   • Examples: subtree_height, is_balanced, max_path_sum_in_subtree.
3. Global State: Update a variable outside the recursion.
   • Examples: max_diameter, result_list.

3. Tree Properties & Types

Not all binary trees are created equal. The structure determines the runtime.

• Perfect: Every level is completely filled. Count = $2^h - 1$.
• Complete: Filled except possibly the last level (nodes aligned left). Heaps are complete trees.
• Balanced: Height is $O(\log N)$. Operations are fast.
• Skewed: Height is $O(N)$. Operations degrade to linked list performance.

4. Common Techniques & Recipes

The "Node-Depth Queue" (Iterative BFS) When solving level-order problems iteratively, store pairs of (node, depth) in your queue.

queue = deque([(root, 0)])
while queue:
    node, depth = queue.popleft()
    # process node at depth
    if node.left: queue.append((node.left, depth + 1))
    if node.right: queue.append((node.right, depth + 1))

The "Parallel Pointers" Strategy For problems involving two trees (e.g., merging, comparing), iterate through both simultaneously.

• If both are BSTs, you can use iterative inorder traversals to treat them like sorted arrays (see Merge Two BSTs).
• If checking for equality, traverse both structure-wise in lockstep.