Tree Traversal Pattern: Template + 225 LeetCode Problems

What the tree traversal pattern is

Almost every binary tree problem is a traversal with a small amount of work attached, so the real decision is when the node gets processed relative to its children. Preorder handles a node before descending and is what you want for copying, serialising, or passing information down from the root. Postorder handles it after both children return and is what you want whenever the answer at a node is computed from its subtrees — heights, diameters, subtree sums, the maximum path sum. Inorder is the special one: on a binary search tree it emits the values in sorted order, which turns validation, the kth smallest, and finding the minimum gap into a single scan with a pointer to the previously visited value. Level order is breadth-first search on a tree, done by draining the queue one full level at a time so each level can be handled as a unit. The iterative inorder is the traversal worth being able to write from memory, because it is the one an interviewer will ask for when recursion is ruled out.

When to use it

• —A value at each node depends on its subtrees — that is postorder.
• —The tree is a BST and the question is about sorted order, a kth element, or a range.
• —The answer is per level, or is the shallowest node satisfying a condition.
• —You are asked to serialise, clone, or rebuild a tree from traversal output.

The tree traversal template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 225 problems listed below.

def inorder(root):
    result, stack, node = [], [], root

    while node or stack:
        while node:                  # descend as far left as possible
            stack.append(node)
            node = node.left

        node = stack.pop()
        result.append(node.val)      # left subtree finished, so visit now
        node = node.right            # then do the same for the right subtree

    return result

Complexity characteristics

Time

O(n)

Auxiliary space

O(h), where h is the height of the tree

Every node is visited exactly once whatever the order, so the time is linear in the node count. The space is the recursion stack or the explicit stack, which is the height of the tree: O(log n) on a balanced tree and O(n) on a degenerate one, and the degenerate one is what a test harness will hand you. Level-order traversal swaps the stack for a queue holding the widest level, which is up to n/2 nodes on a full tree.

All 225 tree traversal LeetCode problems

Every problem in the library the tree traversal pattern applies to, grouped by LeetCode's own difficulty rating. 167 of the 225 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Tree Traversal pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.