Tree Traversal LeetCode Pattern Guide — Preorder, Inorder, Postorder, and Level-Order

A tree traversal LeetCode pattern guide is a guide to information flow. Preorder, inorder, postorder, and level-order are not four arbitrary memorized sequences. They answer different questions about when a node should be processed relative to its children. Preorder is useful when parent context flows down. Inorder is special for binary search trees. Postorder is useful when child results flow up. Level-order is useful when distance from the root matters. Once you choose the flow, the code template is usually small.

Tree traversal LeetCode pattern guide: the traversal decision table

Start with the question the prompt is really asking:

| Problem shape | Traversal | Why | |---|---|---| | Serialize tree, copy tree, root-to-leaf paths | Preorder | Process parent before children | | Validate or iterate BST in sorted order | Inorder | BST inorder yields sorted values | | Compute height, diameter, max path sum | Postorder | Need child values before parent answer | | Delete/free tree, evaluate expression tree | Postorder | Children must be processed first | | Level averages, right side view, minimum depth | Level-order BFS | Need nodes by depth | | Zigzag level order | Level-order with direction | Same depth grouping with ordering twist | | Lowest common ancestor | Postorder-style recursion | Return child findings upward | | Construct tree from traversals | Preorder/inorder or postorder/inorder | Root position plus subtree boundaries |

If the problem says "bottom-up," think postorder. If it says "by level," think BFS. If it says "BST sorted," think inorder. If it says "path from root," think preorder.

Preorder: parent before children

Preorder visits node -> left -> right. It is the traversal for carrying context down the tree. When the parent's value, path, range, or prefix affects children, preorder is a natural fit.

Common preorder problems:

• Binary tree paths.
• Path sum from root to leaf.
• Serialize a tree.
• Clone/copy a tree.
• Validate BST with min/max bounds.
• Flatten binary tree to linked list.
• Prefix-sum path counting with backtracking.

The invariant: when you enter a node, you know the context from ancestors. You update the context, process or record the node, then recurse to children.

Example explanation for root-to-leaf paths: "I maintain the current path as I descend. At each node I append the value. If it is a leaf, I record the path. Then I backtrack before returning so sibling paths do not share state." The backtracking phrase matters. Many bugs come from mutating a list and forgetting to pop.

For BST validation, preorder with bounds is usually stronger than inorder if duplicates or strict inequality rules are tricky. Each recursive call receives (low, high) bounds. The node must satisfy low < node.val < high, then left gets (low, node.val) and right gets (node.val, high).

Inorder: left, node, right

Inorder visits left -> node -> right. In a binary search tree, this produces sorted order. Outside BST problems, inorder is less magically useful than candidates think. Do not choose it just because the input is a binary tree.

Use inorder for:

• Kth smallest in a BST.
• Validate BST by checking sorted sequence.
• Convert BST to sorted list.
• BST iterator.
• Recover swapped nodes in a BST.
• Range sum in BST with pruning.

The BST iterator pattern is a classic iterative inorder. Maintain a stack of left ancestors. next() pops the smallest remaining node, then pushes the left spine of its right child. This gives amortized O(1) next and O(h) space.

The trap is assuming inorder sortedness for non-BST trees. A normal binary tree has no ordering guarantee. If the prompt does not say BST or define ordering, inorder is just one of several traversal sequences.

For kth smallest, you can stop as soon as you visit k nodes. That is O(h + k) time, not necessarily O(n), because you only traverse the left spine and first k visits. Mention this optimization.

Postorder: children before parent

Postorder visits left -> right -> node. It is the most important traversal for tree dynamic programming. If the parent answer depends on child answers, use postorder.

Common postorder problems:

• Maximum depth / height.
• Diameter of binary tree.
• Balanced binary tree.
• Maximum path sum.
• Lowest common ancestor.
• Count nodes matching subtree property.
• Delete leaves with target value.
• House robber on tree.

The pattern is "return one value upward, update another answer globally if needed." Diameter is the clean example. Each node returns its height to the parent, but the global answer may be left_height + right_height through that node. Maximum path sum is similar: return the best one-sided path upward, update global with a path that may use both sides.

This distinction is senior-level clarity. The value you return to the parent is constrained because a parent path can only extend through one child. The value you use to update the answer at the current node may combine both children. Confusing those two is the most common max-path bug.

For balanced tree, postorder can return height or a sentinel like -1 for unbalanced. If either child is unbalanced or heights differ by more than one, return -1. This avoids recomputing heights repeatedly and keeps the solution O(n).

Level-order: breadth by depth

Level-order traversal uses BFS with a queue. It visits all nodes at depth d before depth d+1. Use it whenever the problem groups, compares, or returns values by level.

Common level-order problems:

• Binary tree level order traversal.
• Right side view.
• Average of levels.
• Minimum depth.
• Zigzag traversal.
• Connect next right pointers.
• Largest value in each row.

The standard template is:

1. Initialize queue with root if present.
2. While queue is not empty, record level_size.
3. Loop level_size times to process the current level.
4. Push children for the next level.
5. Append the level result.

Do not use the changing queue length inside the level loop. Capture the size first. That is how you prevent next-level nodes from leaking into the current level.

For right side view, the answer is the last node processed at each level if you traverse left-to-right. Or the first node if you traverse right-to-left. Say which one you are doing.

For minimum depth, BFS is often better than DFS because the first leaf reached by levels is the answer. DFS still works, but it may explore much more of the tree.

Recursive vs iterative traversal

Recursive traversal is concise and usually accepted. Iterative traversal is useful when recursion depth may overflow or when building an iterator.

Iterative preorder is straightforward: stack root, pop node, process it, push right then left so left is processed first.

Iterative inorder uses the left-spine stack. Push all left nodes, pop, process, then move to right.

Iterative postorder is trickier. Options:

• Use two stacks: push root to stack1, move nodes to stack2, push children, then pop stack2.
• Use one stack plus previous pointer to know whether you are returning from children.
• Use modified preorder node-right-left then reverse to get left-right-node.

In interviews, recursive postorder is usually clearer unless explicitly asked for iterative.

Tree DP: the postorder upgrade

Many medium and hard tree problems are tree DP. The template:

1. Define what the recursive function returns to its parent.
2. Recursively get left and right values.
3. Compute the current node's return value.
4. Update any global or outer answer.
5. Return the constrained value upward.

Examples:

| Problem | Return upward | Update answer | |---|---|---| | Diameter | Height | left height + right height | | Max path sum | Best one-sided gain | node + left gain + right gain | | LCA | Found node or ancestor | Return current if both sides hit | | House robber III | Pair: rob, skip | Max of root choices | | Balanced tree | Height or sentinel | Sentinel propagates failure |

For House Robber III, returning a pair is cleaner than using globals: rob = node.val + left.skip + right.skip; skip = max(left) + max(right). This is the right way to talk about independent subtree states.

Null handling and base cases

Tree bugs often live in base cases. Decide what null returns:

• Height: null returns 0 or -1 depending on edge vs node height convention.
• Sum: null returns 0.
• Valid BST bounds: null returns true.
• Max path gain: null returns 0 because negative gains are ignored.
• LCA: null returns null.
• Count: null returns 0.

Be explicit. If height is counted in nodes, leaf height is 1 and null is 0. If height is counted in edges, leaf height is 0 and null is -1. Either convention works if consistent.

For maximum path sum, initialize the answer to negative infinity, not zero. If all node values are negative, the best path is the least negative node. A zero initialization incorrectly allows an empty path.

Common traps in tree traversal

Choosing inorder for a non-BST. Inorder only gives sorted order in BSTs.

Global state not reset. If using class variables in online judges, make sure each test gets a clean answer.

Mutating a shared path. Append/pop correctly or pass a copied path when needed.

Wrong max path return. Do not return a path that branches to both children; parents can only extend one side.

Forgetting null root. Empty tree should not crash.

Level contamination. Capture queue size before processing a level.

Duplicate value assumptions. Tree nodes may have duplicate values; identity is not always value.

Recursion depth. A skewed tree with many nodes may require iterative traversal in production languages.

Prep checklist for traversal problems

Before coding, answer:

• Does information flow down from parent or up from children?
• Is the tree a BST, or just a binary tree?
• Do I need nodes grouped by depth?
• What should the recursive function return?
• Is there a separate global answer?
• What is the null base case?
• Can values be negative or duplicated?
• Do I need to preserve paths independently?
• What is the time and space complexity?

For most tree traversals, time is O(n) because each node is visited once. Space is O(h) recursion stack for DFS, where h is height, or O(w) queue space for BFS, where w is maximum width. In the worst case, both can be O(n).

How to talk about traversal in interviews and resumes

In interviews, name the traversal and why. "I will use postorder because the node's answer depends on the heights of both children." Or: "This is a BST, so inorder gives sorted values and lets us stop at the kth visit." That one sentence shows pattern recognition.

On a resume, avoid saying "implemented tree traversal." Tie it to data or systems:

• "Built hierarchical permission evaluation with postorder aggregation of inherited rules."
• "Implemented level-order traversal to compute organization depth and reporting-layer metrics."
• "Created iterator over sorted tree-backed records using stack-based inorder traversal."

The practical skill is recursive decomposition. Define what each subtree returns, combine those answers at the parent, and protect the edge cases. Once that is clear, preorder, inorder, postorder, and level-order become tools rather than memorized orders.

Related guides

• BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source — A BFS LeetCode pattern guide for recognizing queue-based problems, implementing level-order traversal, solving unweighted shortest paths, using multi-source BFS, and avoiding common visited-state bugs.
• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.
• Binary Search LeetCode Pattern Guide — Bounds, Rotated Arrays, and Search-on-Answer — A binary search LeetCode pattern guide for exact search, lower/upper bounds, rotated arrays, and search-on-answer problems. Includes invariants, templates, traps, and interview-ready explanations.
• Bit Manipulation LeetCode Pattern Guide — XOR Tricks, Masks, and Counting Bits — A practical bit manipulation LeetCode pattern guide covering XOR tricks, masks, counting bits, subset enumeration, flags, and the interview pitfalls around signed integers.
• DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.