LearnDSA.me - Master Data Structures & Algorithms

Tree traversal is the process of visiting each node in a tree data structure exactly once. The order in which nodes are visited defines different traversal algorithms, each useful for different purposes.

Why Traversal Matters:

Access all data in the tree

Search for specific values

Perform operations on each node

Convert tree to other data structures

Two Main Categories:

Depth-First Search (DFS):

Go as deep as possible before backtracking

Types: In-order, Pre-order, Post-order

Breadth-First Search (BFS):

Visit all nodes at current level before going deeper

Also called: Level-order traversal

Sample Tree Structure

Root: Node 1

Height: 2 levels

Complete binary tree - perfect for traversal examples

Depth-First Traversals

In-Order Traversal

Order: Left → Root → Right

Use Case: Get sorted data from BST

Result: [4, 2, 5, 1, 6, 3, 7]

Traversal Animation

Unvisited

Current

Visited

Implementation:

JavaScript

function inorderTraversal(root) {
  const result = [];
  
  function inorder(node) {
    if (node) {
      inorder(node.left);    // Left
      result.push(node.val); // Root
      inorder(node.right);   // Right
    }
  }
  
  inorder(root);
  return result;
}

Complexity: Time: O(n), Space: O(h) where h is height

Breadth-First Traversal

Level-order traversal visits nodes level by level, from left to right. It uses a queue data structure to keep track of nodes to visit next.

Level-Order Algorithm:

1Start with root in queue
2While queue is not empty:
aDequeue node and visit it
bAdd left child to queue (if exists)
cAdd right child to queue (if exists)

Common Applications:

Finding shortest path in unweighted graphs

Level-wise processing (e.g., printing each level)

Finding nodes at a specific distance

Tree serialization/deserialization

Level-Order Traversal

Visit order: [1, 2, 3, 4, 5, 6, 7]

Level 0:

Level 1:

Level 2:

Level-Order Implementation:

JavaScript

function levelorderTraversal(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];
  
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);
    
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  return result;
}

Complexity: Time: O(n), Space: O(w) where w is max width

Implementation Patterns

Recursive vs Iterative:

Recursive (DFS):

Natural, clean code, uses call stack

Space complexity: O(h) for call stack

Iterative (BFS):

Uses explicit queue, more control

Space complexity: O(w) for queue

Common Pitfalls:

Null checks: Always check if node exists before accessing

Base case: Recursive functions need proper termination

Stack overflow: Deep trees can cause stack overflow in recursion

Order matters: Wrong order gives wrong traversal type

Iterative DFS Template:

function iterativeInorder(root) {
  const result = [];
  const stack = [];
  let current = root;
  
  while (current || stack.length > 0) {
    // Go to leftmost node
    while (current) {
      stack.push(current);
      current = current.left;
    }
    
    // Process node
    current = stack.pop();
    result.push(current.val);
    
    // Move to right subtree
    current = current.right;
  }
  
  return result;
}

Performance Comparison:

Method	Time	Space	Notes
Recursive DFS	O(n)	O(h)	Call stack space
Iterative DFS	O(n)	O(h)	Explicit stack
Level-order BFS	O(n)	O(w)	Queue space

h = height of tree, w = maximum width of tree

Previous: Binary Trees Next: Tree Problems

function inorderTraversal(root) { const result = []; function inorder(node) { if (node) { inorder(node.left); // Left result.push(node.val); // Root inorder(node.right); // Right } } inorder(root); return result; }

function levelorderTraversal(root) { if (!root) return []; const result = []; const queue = [root]; while (queue.length > 0) { const node = queue.shift(); result.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } return result; }

function iterativeInorder(root) { const result = []; const stack = []; let current = root; while (current || stack.length > 0) { // Go to leftmost node while (current) { stack.push(current); current = current.left; } // Process node current = stack.pop(); result.push(current.val); // Move to right subtree current = current.right; } return result; }

Method

Time

Space

Notes

Recursive DFS

O(n)

O(h)

Call stack space

Iterative DFS

O(n)

O(h)

Explicit stack

Level-order BFS

O(n)

O(w)

Queue space