[AlgoMastery]
Topics›Queue›Level-Order Traversal
📖

Level-Order Traversal

Queue
~20 min read
5 practice problems

Overview

Level-order traversal (also called breadth-first traversal) processes binary tree nodes level by level, visiting all nodes at depth d before nodes at depth d+1. It uses a queue to maintain the order of nodes to visit, making it perfect for problems requiring level-by-level processing.

Unlike preorder, inorder, or postorder traversals (which are depth-first), level-order traversal explores the tree breadth-first, ensuring you see nodes level by level from top to bottom. This makes it ideal for problems like finding level averages, right-side view, or processing nodes at each level.

Key characteristics:

  • Level-by-level - Process all nodes at current level before next
  • Queue-based - Uses queue for FIFO order
  • Top to bottom - Starts at root, goes level by level
  • Left to right - Within each level, processes left to right
  • Complete - Visits all nodes in the tree

How Level-Order Traversal Works

Level-order traversal follows these steps:

  1. Start with root node, add to queue
  2. While queue is not empty:
  • Get current level size (number of nodes at this level)
  • Process all nodes at current level
  • Add all children of current level nodes to queue
  • Move to next level
  1. Repeat until queue is empty

The queue ensures nodes are processed in level order, maintaining the breadth-first exploration.

Basic Level-Order Traversal

Simple level-order traversal returning values:

class TreeNode {
  val: number;
  left: TreeNode | null = null;
  right: TreeNode | null = null;
  constructor(val: number) {
    this.val = val;
  }
}

function levelOrder(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[] = [];
  
  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;
}

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

Output: [3, 9, 20, 15, 7] for tree:

    3
   / \
  9  20
    /  \
   15   7

Pattern 1: Level-Order with Level Separation

Return nodes grouped by level:

function levelOrderLevels(root: TreeNode | null): number[][] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[][] = [];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];
    
    // Process all nodes at current level
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      
      // Add children for next level
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(level);
  }
  
  return result;
}

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

Output: [[3], [9, 20], [15, 7]]

Key insight: Track levelSize before processing to separate levels.

Pattern 2: Right Side View

Return rightmost node at each level:

function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[] = [];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      
      // Rightmost node at this level
      if (i === levelSize - 1) {
        result.push(node.val);
      }
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  
  return result;
}

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

Output: [3, 20, 7]

Pattern 3: Left Side View

Return leftmost node at each level:

function leftSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[] = [];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      
      // Leftmost node at this level
      if (i === 0) {
        result.push(node.val);
      }
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  
  return result;
}

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

Pattern 4: Average of Levels

Calculate average value at each level:

function averageOfLevels(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[] = [];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    let sum = 0;
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      sum += node.val;
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(sum / levelSize);
  }
  
  return result;
}

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

Output: [3.0, 14.5, 11.0]

Pattern 5: Zigzag Level Order

Traverse level by level, alternating left-to-right and right-to-left:

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[][] = [];
  let leftToRight = true;
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      
      // Add to level based on direction
      if (leftToRight) {
        level.push(node.val);
      } else {
        level.unshift(node.val);
      }
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(level);
    leftToRight = !leftToRight;
  }
  
  return result;
}

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

Output: [[3], [20, 9], [15, 7]]

Pattern 6: Maximum Value at Each Level

Find maximum value at each level:

function largestValues(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[] = [];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    let maxVal = -Infinity;
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      maxVal = Math.max(maxVal, node.val);
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(maxVal);
  }
  
  return result;
}

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

Pattern 7: Minimum Depth

Find minimum depth (distance to nearest leaf):

function minDepth(root: TreeNode | null): number {
  if (!root) return 0;
  
  const queue: [TreeNode, number][] = [[root, 1]];
  
  while (queue.length > 0) {
    const [node, depth] = queue.shift()!;
    
    // Found leaf node
    if (!node.left && !node.right) {
      return depth;
    }
    
    if (node.left) queue.push([node.left, depth + 1]);
    if (node.right) queue.push([node.right, depth + 1]);
  }
  
  return 0;
}

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

Key insight: BFS finds minimum depth because it explores level by level.

Pattern 8: N-ary Tree Level Order

Level-order traversal for N-ary trees:

class NaryNode {
  val: number;
  children: NaryNode[] = [];
  constructor(val: number) {
    this.val = val;
  }
}

function naryLevelOrder(root: NaryNode | null): number[][] {
  if (!root) return [];
  
  const queue: NaryNode[] = [root];
  const result: number[][] = [];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      
      // Add all children
      for (const child of node.children) {
        queue.push(child);
      }
    }
    
    result.push(level);
  }
  
  return result;
}

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

Pattern 9: Level Order Successor

Find next node in level-order traversal after given node:

function levelOrderSuccessor(root: TreeNode | null, target: number): TreeNode | null {
  if (!root) return null;
  
  const queue: TreeNode[] = [root];
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
    
    // If current node is target, next node is successor
    if (node.val === target && queue.length > 0) {
      return queue[0];
    }
  }
  
  return null;
}

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

Pattern 10: Connect Nodes at Same Level

Connect each node to its right neighbor at the same level:

class NodeWithNext {
  val: number;
  left: NodeWithNext | null = null;
  right: NodeWithNext | null = null;
  next: NodeWithNext | null = null;
  constructor(val: number) {
    this.val = val;
  }
}

function connect(root: NodeWithNext | null): NodeWithNext | null {
  if (!root) return null;
  
  const queue: NodeWithNext[] = [root];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      
      // Connect to next node in same level
      if (i < levelSize - 1) {
        node.next = queue[0];
      }
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  
  return root;
}

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

When to Use Level-Order Traversal

Use level-order traversal when you see these signals:

  • "Level by level" - Process nodes level by level
  • "Right side view" or "left side view" - Need nodes at level boundaries
  • "Level average" or "level sum" - Aggregate values at each level
  • "Minimum depth" - Find distance to nearest leaf
  • "Connect nodes" - Link nodes at same level
  • "Zigzag traversal" - Alternate direction per level
  • "Level maximum/minimum" - Find extremum at each level

Key distinction:

  • Level-order (BFS) - Process level by level, queue-based
  • Preorder/Inorder/Postorder (DFS) - Depth-first, stack/recursion-based

Level-Order vs Other Traversals

| Traversal | Order | Data Structure | Use Case |

|-----------|-------|----------------|----------|

| Level-order | Level by level | Queue | Level-based problems |

| Preorder | Root → Left → Right | Stack | Copy tree, prefix expressions |

| Inorder | Left → Root → Right | Stack | BST sorted order |

| Postorder | Left → Right → Root | Stack | Delete tree, postfix expressions |

Remember:

  • Level-order for level-based problems, right/left view, level averages
  • DFS traversals for tree structure problems, BST operations

Template (Basic Level-Order)

function levelOrderTemplate(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[] = [];
  
  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;
}

Template (Level-by-Level)

function levelOrderLevelsTemplate(root: TreeNode | null): number[][] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[][] = [];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(level);
  }
  
  return result;
}

Template (Level with Processing)

function levelOrderProcessTemplate(root: TreeNode | null): void {
  if (!root) return;
  
  const queue: TreeNode[] = [root];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    
    // Process all nodes at current level
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      
      // Process node (e.g., find max, calculate sum)
      // processNode(node);
      
      // Add children for next level
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    // Process level (e.g., add to result, calculate average)
    // processLevel();
  }
}

Time and Space Complexity

Binary Tree Level-Order

  • Time: O(n) where n is number of nodes
  • Space: O(n) worst case (complete binary tree)

N-ary Tree Level-Order

  • Time: O(n) where n is total nodes
  • Space: O(n) worst case

Space analysis:

  • Best case: O(1) for skewed tree (one node per level)
  • Worst case: O(n) for complete binary tree (last level has ~n/2 nodes)
  • Average case: O(n) for balanced trees

Practice Tips

  1. Track level size - Get levelSize = queue.length before processing level
  2. Process level by level - Use for loop with levelSize to process all nodes at current level
  3. Add children after processing - Add children to queue after processing current node
  4. Handle null root - Always check if root is null
  5. Use queue, not stack - Level-order requires FIFO order
  6. Track direction - For zigzag, toggle direction after each level
  7. Early termination - Can return early for problems like minimum depth

Common Mistakes

  1. Not tracking level size - Queue size changes during level processing
  2. Processing while adding - Should process all nodes at level before adding next level
  3. Using stack - Wrong data structure breaks level-order
  4. Not handling null - Forgetting to check node.left and node.right before adding
  5. Wrong loop condition - Using queue.length directly in for loop causes issues
  6. Not resetting level - Forgetting to create new level array for each level
  7. Index errors - Off-by-one when finding rightmost/leftmost node

Real-World Applications

Level-order traversal is used in:

  • Tree Visualization - Display trees level by level
  • Printing Trees - Pretty print trees with indentation
  • Tree Serialization - Serialize tree level by level
  • Level-Based Analysis - Analyze tree structure by level
  • Tree Balancing - Check if tree is balanced level by level
  • Hierarchical Data - Process organizational hierarchies
  • File System Traversal - Traverse directory structure level by level
  • Network Topology - Analyze network structure by hops

Related Concepts

  • Breadth-First Search (BFS) - Same algorithm, different context (graphs)
  • Queue - Data structure used for level-order traversal
  • Tree Traversals - Preorder, inorder, postorder (DFS)
  • Binary Tree - Most common tree structure for level-order
  • N-ary Tree - Generalization to multiple children
  • Minimum Depth - Level-order finds minimum depth efficiently

Summary

Level-order traversal is a fundamental tree traversal technique:

  • Queue-based - Uses queue for FIFO order
  • Level-by-level - Processes all nodes at current level before next
  • Top to bottom - Starts at root, goes level by level
  • Complete - Visits all nodes in the tree
  • Essential - Foundation for many tree problems

Key takeaways:

  • Track level size before processing each level
  • Process all nodes at current level before adding next level
  • Use queue (not stack) for level-order traversal
  • Essential for level-based problems (right view, averages, etc.)
  • Foundation for BFS on trees

Mastering level-order traversal will help you solve level-based tree problems efficiently in coding interviews.

← PreviousBreadth-First Search (BFS)Next →Circular Queue