Binary Tree Traversal

Description

Binary tree traversal is recursion shaped like the tree. Handle the empty tree, recurse into the left and right subtrees, and combine. Almost every tree problem takes one of two shapes. In the bottom-up shape, the children report results and the parent combines them (height, size, balance). In the top-down shape, the parent passes rules down to its children (a BST's valid range, the depth so far). Picking the right shape is most of the work.

We'll go from simple to more technical:

1. The pattern: null base case, recurse, combine results on the way up.
2. A second flavor: pass constraints down instead (validating a BST).
3. Where tree walks run in production (DOMs, file systems, permissions).
4. The bugs: missing base cases, local-only checks, and recomputing subtrees.

The approach

A tree has no single "front to back" order the way an array does. But every subtree is a smaller tree, so recursion fits it naturally. First decide what an empty tree returns. Then ask both subtrees for their answers, and combine them with the node itself.

The height of a tree is the number of nodes on its longest path down from the root. An empty tree has height 0. Any other tree has height 1 plus the taller of its two subtrees.

The answers come back from the bottom up:

int height(TreeNode node) {
    if (node == null) return 0;               // an empty tree has height 0
    int left = height(node.left);
    int right = height(node.right);
    return 1 + Math.max(left, right);          // combine: this node plus the taller side
}

def height(node: TreeNode | None) -> int:
    if node is None:
        return 0                               # an empty tree has height 0
    left = height(node.left)
    right = height(node.right)
    return 1 + max(left, right)                # combine: this node plus the taller side

Size, sum and balance checks are the same shape with a different combine step.

A second flavor: passing constraints down

Some problems need the other direction. Each call receives rules from its ancestors and passes a stricter version to its children. Validating a binary search tree is the clearest case. In a BST, everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. Comparing a node with its parent isn't enough.

Take a root of 10 whose left child is 5, and give 5 a right child of 12. Each node looks fine next to its parent: 12 is bigger than 5. But 12 sits in 10's left subtree, so it must be smaller than 10. Carrying an allowed range down catches it:

boolean isValidBST(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return isValidBST(node.left, min, node.val)      // left subtree: same lower bound, tighter upper bound
        && isValidBST(node.right, node.val, max);    // right subtree: tighter lower bound, same upper bound
}

def is_valid_bst(node: TreeNode | None, lo: float = float("-inf"), hi: float = float("inf")) -> bool:
    if node is None:
        return True
    if not lo < node.val < hi:
        return False
    return (is_valid_bst(node.left, lo, node.val)       # left subtree: same lower bound, tighter upper bound
            and is_valid_bst(node.right, node.val, hi))  # right subtree: tighter lower bound, same upper bound

Each step down narrows the range. A node deep in the left subtree still has to respect the root's upper bound, set many calls earlier.

Where you'll see it

Every hierarchy is walked this way: an HTML or JSON document, a file system, a folder tree with permissions. Permission inheritance is the top-down shape. A folder's effective permissions combine the rules of every folder above it, not just its parent's.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A recursive tree function reads node.val without checking for null first. What happens?

2. A BST check only tests node.left.val < node.val < node.right.val at each node. Why does it miss invalid trees?

3. Why pass a shrinking (min, max) range down instead of comparing with one value?

Key takeaways

• Most tree problems are bottom-up (combine the children's answers) or top-down (pass rules down as parameters).
• Height, size and sums are bottom-up. BST validation is top-down.
• A node can satisfy its parent and still break an older ancestor's rule. Carry the full range down.
• Decide what an empty tree returns before reading any node's fields.
• Calling a helper recursion at every node turns O(n) into O(n log n), or O(n^2) on a skewed tree.