Trees & Traversals

How to recognize it

Anything with "node," "root," "parent," or "binary tree" in the prompt is a tree problem. The next question to ask yourself is whether the problem cares about depth (deepest path, path sum, is this a valid binary search tree) — usually depth-first — or level (level-order output, minimum depth, right-side view) — usually breadth-first. Getting that choice right before coding saves a rewrite partway through.

How the pattern works

A representative depth-first problem: check whether a binary tree is height-balanced (the height difference between left and right subtrees never exceeds 1, at every node). The naive approach recomputes height at every node — O(n²) in the worst case. The better approach computes height and checks balance in a single bottom-up (post-order) pass, returning -1 as a sentinel the moment imbalance is found anywhere below.

def is_balanced(root):
    def height(node):
        if not node:
            return 0
        left = height(node.left)
        if left == -1:
            return -1
        right = height(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        return max(left, right) + 1

    return height(root) != -1

function isBalanced(root) {
  function height(node) {
    if (!node) return 0;
    const left = height(node.left);
    if (left === -1) return -1;
    const right = height(node.right);
    if (right === -1) return -1;
    if (Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
  }

  return height(root) !== -1;
}

Say what the sentinel means before you write it: "I'll return -1 to mean 'already found imbalance below,' so I don't need a separate boolean flag threaded through every call." Interviewers who ask you to make this iterative later are checking whether you understand that this sentinel-and-short-circuit is exactly what an explicit stack has to replicate manually.

Common mistakes

• Recomputing height (or any subtree property) from scratch at every node instead of combining the computation with the traversal that already visits every node once
• Confusing pre-order, in-order, and post-order when the problem specifically needs one — in-order on a binary search tree yields sorted order, which is the whole point of several BST questions
• Forgetting the null/leaf base case, causing infinite recursion or a crash on an empty tree
• Using recursion depth as if it were free — a skewed tree of depth n will blow the call stack in languages without tail-call optimization, worth mentioning if asked about extremely unbalanced input

Complexity

Most tree traversals are O(n) time, since each node is visited a constant number of times. Space is where it gets interesting: O(h) for the recursion or explicit stack, where h is the tree's height — O(log n) for a balanced tree, but O(n) in the worst case for a completely skewed one. Naming that height-dependent space bound, not just "O(log n)" by reflex, is what separates a memorized answer from an understood one — see Time & Space Complexity.