Trees

When to reach for it

• Hierarchies: org charts, folder trees, comment threads, document outlines, parsed expressions.
• Questions about depth, height, paths, subtrees, ancestors or levels.
• Searching or checking a binary search tree.
• Writing a structure out and rebuilding it exactly.

The core idea

Write a function that answers the question for one node, assuming it already has the answers for the left and right subtrees. That gives a post-order recursion: compute the children, combine, return. Decide what flows in which direction: values that come down from ancestors (the highest value seen so far, the range a BST node must fall in) become parameters; values that come up from descendants (heights, counts, sizes) become return values.

Use breadth-first search with a queue when the question is about levels: the view from one side, the shallowest leaf, an average per level. Read the queue's length at the start of each round and process exactly that many nodes, so each round is one level.

A Python template

from collections import deque

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

def diameter(root):
    """Edges on the longest path between any two nodes."""
    best = 0
    def depth(node):                      # returns height, updates best
        nonlocal best
        if node is None:
            return 0
        left, right = depth(node.left), depth(node.right)
        best = max(best, left + right)    # the longest path through node
        return 1 + max(left, right)
    depth(root)
    return best

def count_unbeaten(node, highest=float("-inf")):
    """Nodes whose value is at least every value above them."""
    if node is None:
        return 0
    here = 1 if node.val >= highest else 0
    highest = max(highest, node.val)      # flows down as a parameter
    return here + count_unbeaten(node.left, highest) + count_unbeaten(node.right, highest)

def right_side_view(root):
    view, queue = [], deque([root] if root else [])
    while queue:
        for i in range(len(queue)):       # exactly one level per round
            node = queue.popleft()
            if i == 0:
                view.append(node.val)     # right children go in first
            queue.extend(c for c in (node.right, node.left) if c)
    return view

Time and space

Every traversal visits each node once: O(n) time. Recursion uses O(h) stack space, where h is the height: O(log n) for a balanced tree, O(n) for one that is a straight line. Breadth-first search holds at most one level at a time, O(w) for the widest level.

Common mistakes

• Checking a BST node only against its direct children; the allowed range has to flow down from every ancestor.
• Forgetting the empty-tree base case, or returning the wrong value from it.
• Mixing up what flows down as a parameter and what flows up as a return value.
• Claiming O(log n) depth without saying the tree is balanced.
• Recursing on a very deep, skewed tree in Python, which can hit the recursion limit; an explicit stack avoids it.

How to explain it out loud

Say the recursive contract before you write it: "depth of a node returns the number of nodes on the longest path down from it; for an empty subtree it's zero." A clear contract makes the code nearly write itself, and it is exactly what interviewers mean by explaining your approach.

Then trace a tree of three or four nodes, saying what each call returns, and call out the skewed case for space and the empty tree. When Josh asks why a BST check passes a range down, "because a node must be smaller than every ancestor it sits to the left of, not just its parent" is the kind of answer Devana scores as code defense.