Tree Traversal Pattern

Why this pattern matters for LeetCode

Beginners try to handle trees iteratively without a plan and lose track of which nodes were visited. DFS recursion is natural for trees because each call handles one node and delegates to its subtrees. The call stack becomes the traversal stack automatically — you don't manage it. Most binary tree problems are a DFS with one specific operation per node: compare, swap, accumulate, validate. Nail the DFS template and most tree problems become straightforward.

What the Tree Traversal pattern is

Tree traversal means visiting every node in a tree systematically. Depth-first search (DFS) goes deep before wide — preorder visits the root first, inorder visits left-root-right (natural for BSTs), postorder visits children before parent. Breadth-first search (BFS) visits all nodes at one depth before moving to the next, using a queue. Most binary tree problems are a DFS traversal with a specific operation at each node.

Reach for Tree Traversal when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Tree Traversal

• ✓DFS preorder — process node before children: serialize a tree, print top-down
• ✓DFS inorder — process left, then node, then right: BST in sorted order, validate BST
• ✓DFS postorder — process children before node: compute height, delete tree, Invert Binary Tree
• ✓BFS level-order — process all nodes at depth d before depth d+1: level-order traversal, minimum depth, right side view

When NOT to use Tree Traversal

• ✕The input is not a tree — if there are cycles, use graph traversal with a visited set
• ✕You only need a specific node and can short-circuit early — full traversal wastes time
• ✕The tree is so deep that recursion hits a stack overflow — consider iterative DFS with an explicit stack
• ✕The problem requires a different data structure entirely

Better alternative: In those cases, iterative DFS with an explicit stack or BFS with a queue avoids recursion depth limits.

JavaScript code template

DFS template + Invert Binary Tree example — O(n) time, O(h) space

// Generic DFS template
function dfs(node) {
  if (node === null) return; // base case: empty subtree — always handle first

  // PREORDER: do work here (before recursing)
  dfs(node.left);
  // INORDER: do work here (between left and right)
  dfs(node.right);
  // POSTORDER: do work here (after both children return)
}

// Invert Binary Tree — postorder DFS
function invertTree(root) {
  if (root === null) return null;

  // Recurse into children first (postorder)
  const left = invertTree(root.left);
  const right = invertTree(root.right);

  // Swap after children are fully inverted
  root.left = right;
  root.right = left;

  return root;
}

The null check is the first thing — always. Without it, you'll crash on leaf node children. For Invert Binary Tree, postorder is correct: recurse into both subtrees first, then swap. If you swap first (preorder) and then recurse, you pass the already-swapped children to the recursive calls, producing a wrong result.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Handle the null base case first — return null, 0, true, or whatever makes sense for the empty subtree.
2. 2Recurse into the left subtree and capture the result.
3. 3Recurse into the right subtree and capture the result.
4. 4Do the work at the current node: compare, swap, accumulate — decide if it's pre, in, or postorder.
5. 5Return the result upward to the parent call.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Invert Binary Tree

  Postorder DFS: recurse into both subtrees first, then swap left and right children.

  Premium→
• Maximum Depth of Binary Tree

  Return 1 + max(leftDepth, rightDepth) at each node — the answer bubbles up from the leaves.

  Premium→
• Same Tree

  Simultaneously recurse both trees and compare values at each matching node.

  Premium→

Coming soon

• Symmetric Tree

  Compare mirror-image nodes — the left subtree's left against the right subtree's right.

  Coming soon
• Binary Tree Level Order Traversal

  BFS with a queue — process all nodes at each depth before moving to the next level.

  Coming soon

Common mistakes beginners make

• ✕Forgetting the null base case — without it, node.left and node.right on a null node crashes immediately.
• ✕Not returning the result of recursive calls when the function needs to return a value — the recursive result gets computed but discarded.
• ✕Swapping left and right before recursing into them instead of after — you end up passing already-modified subtrees to the recursive calls.
• ✕Using BFS when the problem needs path information — DFS naturally tracks the path via the call stack; BFS doesn't store paths.

DFS vs BFS

Choose the right tool for the job.

Time and space complexity

Every node is visited exactly once — O(n) time. Space is the recursion call stack depth, which equals the tree height h. For a balanced tree, h = O(log n). For a skewed tree (essentially a linked list), h = O(n). BFS uses O(w) space where w is the maximum width of the tree.

Frequently asked questions

When should I use DFS vs BFS for tree problems?

Use DFS when the problem involves paths, depth, or subtree structure — the call stack naturally tracks 'where you came from.' Use BFS when the problem is level-based: level-order traversal, minimum depth, right side view. A queue gives you nodes in level order; recursion gives you nodes in depth order.

What's the difference between preorder, inorder, and postorder?

Preorder: process the root, then left subtree, then right — good for serialization, copying. Inorder: left subtree, then root, then right — produces sorted order for BSTs. Postorder: left subtree, right subtree, then root — good when you need child results before you can process the parent (height, Invert Binary Tree).

Why is recursion so natural for trees?

Because trees are defined recursively — a tree is a node with a left subtree and a right subtree, each of which is also a tree. Recursion mirrors this definition exactly: handle the current node, delegate to left, delegate to right. The call stack automatically tracks the path from root to current node.

What happens if I forget the null check?

You'll get a runtime error as soon as the recursion reaches a leaf node and tries to access node.left or node.right on null. The null check (if node === null) is the base case that stops the recursion. Without it, the recursion continues past the leaves and crashes.

Should I use recursion or iterative DFS?

For most LeetCode problems, recursion is cleaner and correct. The risk of stack overflow only appears with extremely deep trees (depth > ~10,000), which doesn't happen in standard LeetCode tests. If a problem specifically says 'solve iteratively,' use an explicit stack array to simulate the call stack.