Algorithm • medium

Tree Traversal (DFS/BFS) Complete Guide

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)`

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

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

Channel: mycodeschool

Full video link:

https://www.youtube.com/watch?v=9RHO6jU--GU

Tree Traversal Visualizer

Compare queue-based BFS vs stack/recursion-style DFS traversal order.

Tree Traversal VisualizerStep 1 / 3

Breadth-first starts from root and visits level by level.

Tree Nodes

A -> {B, C}, B -> {D, E}, C -> {F}

Queue

[A]

Visited

[]

Strategy

Pop front, push children to back.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

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.

Putting It All Together

This walkthrough connects the core concepts of Tree Traversal (DFS/BFS) into one end-to-end execution flow.

Step 1

Root node

Top entry node for traversal.

Before

DFS stack =

Tree root = 10

→

After

Visit sequence grows
Stack contains next depth branch

Transition

Pop top node

→Push children in reverse visit order

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

Step 2

Children

Descendant references explored per traversal order.

Before

Queue for BFS =

Need level-order traversal

→

After

Current level finished
Queue holds next level nodes

Transition

Dequeue front node

→Enqueue left then right child

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

Step 3

Traversal order

Sequence rule defining visitation order.

Before

Inorder traversal on BST
Goal: sorted node values

→

After

Output is non-decreasing
BST property verified

Transition

Traverse left subtree

→Visit node

→Traverse right subtree

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

Step 4

Visited state

Tracking to prevent reprocessing in generalized graphs.

Before

Recursive DFS call(node)
Base case: node == null

→

After

All reachable nodes visited once
Time complexity O(n)

Transition

Process current node

→Recurse into child nodes

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

How It Compares

vs Graph traversal

When to choose this: Choose tree traversal when structure is acyclic and rooted.

Tradeoff: Graph traversal requires explicit visited handling for cycles.

vs Array scan

When to choose this: Choose tree traversal for hierarchical relationships.

Tradeoff: Array scan is simpler for flat data.

vs Topological sort

When to choose this: Choose tree traversal for strict parent-child trees.

Tradeoff: Topological sort handles general DAG dependency graphs.

Real-World Stories and Company Examples

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.

Implementation Guide

Use explicit stack to simulate recursive inorder walk.

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

Language

Iterative inorder traversal

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
}

Common Problems and Failure Modes

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.

Tips and Tricks

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.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

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 (including 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.

LeetCode Progression (Easy to Hard)

Back to DSA Guide Catalog

#	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)`