Trees and recursion

A tree is a graph with no loops, where everything hangs off one root. File systems, org charts, page hierarchies and comments with replies are all trees. Recursion fits them well, because every subtree is just a smaller tree.

Most tree problems come down to deciding what each node should return to its parent. Then you let recursion handle the rest. Finding the lowest common ancestor of two nodes is a classic example:

def lowest_common_ancestor(root, a, b):
    if root is None or root is a or root is b:
        return root
    left = lowest_common_ancestor(root.left, a, b)
    right = lowest_common_ancestor(root.right, a, b)
    if left and right:
        return root  # a and b are on different sides.
    return left or right

Each call reports whether it found a or b below it. The first node where both sides found something is the answer.

Recursion is the cleanest way to write most tree code, but a very deep tree can blow the call stack. If depth could be in the hundreds of thousands, use a loop with your own stack.

• Say what your recursive function returns before writing it.
• Ask if it's a binary tree, and whether nodes know their parent.
• Time is usually O(n). Space is the tree's height, because of the call stack.

Is this a valid binary search tree?

Given the root of a binary tree, check that every node's value is greater than everything in its left subtree and less than everything in its right subtree.

1. The tempting version checks each node against its two children only. That misses a case: a node deep on the left can be bigger than the root.
2. So think about what each node needs from its parent. Every node has to sit inside a range: greater than some lower bound and less than some upper bound.
3. The root's range is (-infinity, infinity). Going left, the upper bound becomes the current value. Going right, the lower bound becomes the current value.
4. Recurse with valid(node, low, high). An empty node is valid. Otherwise check low < node.value < high, then check both children with their new ranges.
5. Take a root of 10 with a left child of 5, and 5 has a right child of 12. 12 is a valid right child of 5, but its range is (5, 10), so it fails. That's the case the tempting version misses.
6. Each node is visited once, so it's O(n) time, and O(height) space for the call stack.
7. Another way to see it is that an inorder traversal of a valid BST is strictly increasing, so you can check each value against the previous one.

Things interviewers tend to ask once you've brought this up.

How would you find the diameter of a tree?

Each node returns its height to its parent, and while it's there it updates a global best with left height plus right height. It's a single postorder pass.

How do you serialize a tree and rebuild it?

A preorder traversal that writes a marker for empty children. Reading it back in the same order rebuilds the exact shape.

What if the tree isn't binary, like an org chart?

Same idea: loop over the children instead of left and right. Problems like 'max party fun where you can't invite a manager and their report' return two values per node, with and without that node.

How do you avoid stack overflow on a very deep tree?

Rewrite it with your own stack. Postorder is the fiddliest. One trick is to do a modified preorder (node, right, left) and reverse the result.

• Only comparing a node to its direct children when the rule applies to whole subtrees.
• Not saying what the recursive function returns.
• Forgetting the empty-tree case.
• Saying space is O(1) when the call stack is O(height).
• Assuming a tree is balanced when it could be one long chain.

• Graph traversal and shortest pathsBFS, DFS and Dijkstra, and when to use each.
• Dynamic programmingSolve each subproblem once and reuse the answer.
• Binary searchCut the search in half, even when you're searching for an answer.