Tree Traversal (DFS/BFS) Complete Guide

Algorithm • medium

Tree traversal means visiting every node in a deliberate order such as preorder, inorder, postorder, or level-order.

Different orders serve different tasks: expression evaluation, sorted output, serialization, and breadth metrics.

Mastering traversal unlocks many tree-based algorithm questions quickly.

Typical Complexity Baseline

Metric	Value
Visit all nodes	`O(n)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Tree traversal preorder visit

Each node is visited once. The order (pre/in/post) decides when the parent is read.

Step 1/15Preorder DFS starts at root A: visit, then recurse left, then right.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Binary tree traversal - breadth-first and depth-first strategies

Channel: mycodeschool

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Root node

What it is Top entry node for traversal.

Why it matters Root node is a required building block for understanding how Tree Traversal (DFS/BFS) stays correct and performant on large inputs.

Children

What it is Descendant references explored per traversal order.

Why it matters Children is a required building block for understanding how Tree Traversal (DFS/BFS) stays correct and performant on large inputs.

Traversal order

What it is Sequence rule defining visitation order.

Why it matters Traversal order is a required building block for understanding how Tree Traversal (DFS/BFS) stays correct and performant on large inputs.

Visited state

What it is Tracking to prevent reprocessing in generalized graphs.

Why it matters Visited state is a required building block for understanding how Tree Traversal (DFS/BFS) stays correct and performant on large inputs.

Work structure

What it is Call stack/explicit stack/queue depending on traversal type.

Why it matters Work structure is a required building block for understanding how Tree Traversal (DFS/BFS) stays correct and performant on large inputs.

Preorder

What it is Visit node before children.

Why it matters Visit node before children. In Tree Traversal (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

Inorder

What it is Visit left node, root, then right (BST yields sorted order).

Why it matters Visit left node, root, then right (BST yields sorted order). In Tree Traversal (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

Postorder

What it is Visit children before node.

Why it matters Visit children before node. In Tree Traversal (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

Level-order

What it is Visit by depth using queue (BFS).

Why it matters Visit by depth using queue (BFS). In Tree Traversal (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

Height

What it is Longest downward path length from node.

Why it matters Longest downward path length from node. In Tree Traversal (DFS/BFS), this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/15

Preorder DFS starts at root A: visit, then recurse left, then right.

Step 2/15

Visit B. Output so far: [A, B].

Step 3/15

Visit D. Output so far: [A, B, D].

Step 4/15

Visit H. Output so far: [A, B, D, H].

Step 5/15

Visit I. Output so far: [A, B, D, H, I].

Step 6/15

Visit E. Output so far: [A, B, D, H, I, E].

Step 7/15

Visit J. Output so far: [A, B, D, H, I, E, J].

Step 8/15

Visit K. Output so far: [A, B, D, H, I, E, J, K].

Step 9/15

Visit C. Output so far: [A, B, D, H, I, E, J, K, C].

Step 10/15

Visit F. Output so far: [A, B, D, H, I, E, J, K, C, F].

Step 11/15

Visit L. Output so far: [A, B, D, H, I, E, J, K, C, F, L].

Step 12/15

Visit M. Output so far: [A, B, D, H, I, E, J, K, C, F, L, M].

Step 13/15

Visit G. Output so far: [A, B, D, H, I, E, J, K, C, F, L, M, G].

Step 14/15

Visit N. Output so far: [A, B, D, H, I, E, J, K, C, F, L, M, G, N].

Step 15/15

Visit O. Output so far: [A, B, D, H, I, E, J, K, C, F, L, M, G, N, O].

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Graph traversal

Choose this when Choose tree traversal when structure is acyclic and rooted.

Tradeoff Graph traversal requires explicit visited handling for cycles.

vs. Array scan

Choose this when Choose tree traversal for hierarchical relationships.

Tradeoff Array scan is simpler for flat data.

vs. Topological sort

Choose this when Choose tree traversal for strict parent-child trees.

Tradeoff Topological sort handles general DAG dependency graphs.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Google Chrome

DOM and render trees are traversed repeatedly for layout and paint phases.

Takeaway Efficient traversal directly impacts UI responsiveness.

MongoDB

Query planner and index structures rely on tree walks to resolve key ranges.

Takeaway Traversal strategy influences database query latency.

Unity

Scene graph processing traverses hierarchical object trees each frame.

Takeaway Predictable traversal ordering is critical for real-time systems.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Use explicit stack to simulate recursive inorder walk.

Complexity: Time O(n), Space O(h)

Iterative inorder traversal

Language

type TreeNode = { value: number; left: TreeNode | null; right: TreeNode | null }

function inorderValues(rootNode: TreeNode | null): number[] {
  const stack: TreeNode[] = []
  const values: number[] = []
  let currentNode = rootNode

  while (currentNode || stack.length > 0) {
    while (currentNode) {
      stack.push(currentNode)
      currentNode = currentNode.left
    }
    const node = stack.pop()!
    values.push(node.value)
    currentNode = node.right
  }

  return values
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Using recursion without considering deep-tree stack limits.
Wrong traversal order for task goal.
Not checking null nodes consistently.
Mixing DFS and BFS state updates.
Mutating tree during traversal without safety plan.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Pick traversal order based on output requirement, not habit.
For level-wise requirements, BFS queue is usually simpler than DFS bookkeeping.
When recursion is used, define base case before writing recursive calls.
Store path state explicitly when questions ask for root-to-leaf constraints.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Systematic way to process hierarchical data structures.
Foundation for BST operations, syntax trees, and scene graph processing.
Supports both recursive and iterative implementations.

LeetCode-specific tips (pattern-identification signals)

Identification signal: data is hierarchical parent-child and every node/path must be visited with an order.
Identification signal: level-order output suggests BFS; subtree/path recursion cues DFS.
If you need depth, ancestor paths, or subtree aggregation, tree traversal is usually the core.
For Tree Traversal (DFS/BFS) questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Maximum Depth of Binary Tree	Easy	`O(n)`
2	Invert Binary Tree	Easy	`O(n)`
3	Binary Tree Inorder Traversal	Easy	`O(n)`
4	Binary Tree Level Order Traversal	Medium	`O(n)`
5	Validate Binary Search Tree	Medium	`O(n)`
6	Lowest Common Ancestor of a Binary Tree	Medium	`O(n)`
7	Binary Tree Right Side View	Medium	`O(n)`
8	Serialize and Deserialize Binary Tree	Hard	`O(n)`
9	Binary Tree Maximum Path Sum	Hard	`O(n)`
10	Recover Binary Search Tree	Hard	`O(n)`