Level Order Tree Traversal

Learn Level Order Tree Traversal with practical examples, explanations, best practices, and real-world coding techniques.

What Is Level-Order Traversal?

Level-order traversal is a tree traversal technique that visits nodes one level at a time, starting from the root and moving downward. Nodes at the same depth are processed before nodes at the next level.

Unlike inorder, preorder, and postorder traversal, which are depth-first techniques, level-order traversal uses a breadth-first approach. 

Top → Bottom
Left → Right within each level

A queue is commonly used to implement level-order traversal because a queue follows the First-In, First-Out principle. Nodes are processed in the same order in which their children are discovered.

Example Binary Tree

Consider the following binary tree: 

          50
         /  \
       30    70
      /  \  /  \
    20   40 60   80

The tree contains three levels: 

Level 0: 50
Level 1: 30, 70
Level 2: 20, 40, 60, 80

Therefore, level-order traversal produces: 

50 → 30 → 70 → 20 → 40 → 60 → 80

How Level-Order Traversal Works

The basic process is:

  1. Put the root node into a queue.
  2. Remove the first node from the queue.
  3. Process that node.
  4. Add its left child to the queue if it exists.
  5. Add its right child to the queue if it exists.
  6. Repeat until the queue is empty.

Because nodes are removed from the front of the queue and their children are added to the back, nodes are naturally processed level by level.

Tracing the Queue

For the example tree, the traversal begins with the root: 

Queue:
[50]

Remove 50 and process it. Its children, 30 and 70, are added to the queue. 

Result: 50
Queue: [30, 70]

Remove 30. Its children, 20 and 40, are added after the nodes already waiting in the queue. 

Result: 50, 30
Queue: [70, 20, 40]

Next, 70 is processed and its children are added. 

Result: 50, 30, 70
Queue: [20, 40, 60, 80]

The remaining nodes are processed in the same way: 

20 → 40 → 60 → 80

Basic JavaScript Implementation

A queue can be represented using an array. Instead of repeatedly removing the first array element, an index can be used to track the next node to process. 

function levelOrder(root) {
  if (root === null) {
    return [];
  }

  const queue = [root];
  const result = [];
  let index = 0;

  while (index < queue.length) {
    const node = queue[index++];

    result.push(node.value);

    if (node.left !== null) {
      queue.push(node.left);
    }

    if (node.right !== null) {
      queue.push(node.right);
    }
  }

  return result;
}

Using an index avoids repeatedly calling shift() on a JavaScript array. The index simply moves forward as nodes are processed.

Level-by-Level Output

Sometimes an application needs the nodes grouped by their levels rather than returned as one flat sequence. 

[
  [50],
  [30, 70],
  [20, 40, 60, 80]
]

To produce this format, the algorithm records the number of nodes currently present in the queue before processing each level. 

function levelOrderByLevel(root) {
  if (root === null) {
    return [];
  }

  const queue = [root];
  const result = [];
  let index = 0;

  while (index < queue.length) {
    const levelSize = queue.length - index;
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue[index++];

      level.push(node.value);

      if (node.left !== null) {
        queue.push(node.left);
      }

      if (node.right !== null) {
        queue.push(node.right);
      }
    }

    result.push(level);
  }

  return result;
}

Why Level Size Matters

The expression queue.length - index represents the number of unprocessed nodes belonging to the current level. Storing that value before processing the level prevents newly discovered child nodes from being mixed into the current level.

For example, when processing level 1: 

Current level:
30, 70

New nodes discovered:
20, 40, 60, 80

The children are added to the queue, but they belong to the next level and are therefore processed only after 30 and 70 have been completed.

Finding the Height of a Tree

Level-order traversal can be used to process a tree one level at a time. This makes it useful for calculating the number of levels or the height of a binary tree. 

function treeHeight(root) {
  if (root === null) {
    return 0;
  }

  const queue = [root];
  let index = 0;
  let height = 0;

  while (index < queue.length) {
    const levelSize = queue.length - index;

    for (let i = 0; i < levelSize; i++) {
      const node = queue[index++];

      if (node.left !== null) {
        queue.push(node.left);
      }

      if (node.right !== null) {
        queue.push(node.right);
      }
    }

    height++;
  }

  return height;
}

Each completed iteration represents one level of the tree, so the height increases once for every level processed.

Finding the Minimum Depth

Level-order traversal is also useful for finding the minimum depth of a binary tree. Since nodes are visited from the root downward, the first leaf encountered is located at the minimum depth. 

function minDepth(root) {
  if (root === null) {
    return 0;
  }

  const queue = [{ node: root, depth: 1 }];
  let index = 0;

  while (index < queue.length) {
    const { node, depth } = queue[index++];

    if (node.left === null && node.right === null) {
      return depth;
    }

    if (node.left !== null) {
      queue.push({
        node: node.left,
        depth: depth + 1
      });
    }

    if (node.right !== null) {
      queue.push({
        node: node.right,
        depth: depth + 1
      });
    }
  }

  return 0;
}

Level-Order Traversal and Binary Search Trees

Level-order traversal can be applied to a Binary Search Tree, but it does not produce sorted values. Instead, it shows the structure of the tree from the top level downward. 

BST:

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

Level-order:

50, 30, 70, 20, 40, 60, 80

This makes level-order traversal useful when the physical or hierarchical shape of the tree is more important than sorted ordering.

Breadth-First Search

Level-order traversal is the binary-tree form of breadth-first search. Both techniques explore nodes according to their distance from the starting point and commonly use a queue.

Characteristic Level-Order Traversal Depth-First Traversal
Strategy Level by level Branch by branch
Typical structure Queue Stack or recursion
Traversal type Breadth-first Depth-first
Typical tree traversal Level-order Inorder, preorder, postorder

Level-Order Traversal Complexity

A complete level-order traversal visits every node once, so the time complexity is O(n), where n is the number of nodes.

The queue can contain nodes from one or more adjacent levels. The maximum number of nodes stored at once is related to the maximum width of the tree.

Operation Complexity
Visit every node O(n)
Queue space O(w)

Here, w represents the maximum width of the tree, meaning the largest number of nodes present at any level.

Level-Order Traversal in Real Applications

Level-order traversal is useful when hierarchical data needs to be processed according to depth or distance from a starting node.

  • Finding the shortest path in an unweighted tree
  • Processing hierarchical data level by level
  • Finding minimum depth
  • Finding the maximum width of a tree
  • Printing tree structures level by level
  • Tree-based coding interview problems
  • Breadth-first search in tree structures

Common Level-Order Traversal Mistakes

  • Using a stack instead of a queue for standard level-order traversal.
  • Processing child nodes before all nodes at the current level.
  • Forgetting to handle an empty tree.
  • Using shift() repeatedly on a large JavaScript array without considering its cost.
  • Failing to capture the current level size when grouped output is required.
  • Assuming level-order traversal produces sorted values for a BST.
  • Confusing breadth-first traversal with depth-first traversal.

Level-Order vs Depth-First Traversal

The main difference is how nodes are explored. Level-order traversal completes one depth level before moving deeper, while depth-first traversal follows a branch as far as possible before returning.

Traversal Order Main Data Structure
Level-order Level by level Queue
Preorder Root → Left → Right Stack / recursion
Inorder Left → Root → Right Stack / recursion
Postorder Left → Right → Root Stack / recursion

Key Takeaways

  • Level-order traversal visits nodes level by level from top to bottom.
  • Nodes at the same depth are processed before nodes at the next depth.
  • It is a breadth-first traversal technique.
  • A queue is the standard data structure used for level-order traversal.
  • Level-order traversal can return a flat sequence or grouped levels.
  • Capturing the current queue size makes level-by-level processing possible.
  • It is useful for minimum depth, tree width, and other breadth-based problems.
  • Level-order traversal of a BST does not produce sorted values.
  • A complete traversal takes O(n) time.
  • Queue space is O(w), where w is the maximum width of the tree.

Code Examples 

function levelOrder(root) {
  if (root === null) {
    return [];
  }

  const queue = [root];
  const result = [];
  let index = 0;

  while (index < queue.length) {
    const node = queue[index++];

    result.push(node.value);

    if (node.left !== null) {
      queue.push(node.left);
    }

    if (node.right !== null) {
      queue.push(node.right);
    }
  }

  return result;
}

console.log(levelOrder(root));
    
function levelOrderByLevel(root) {
  if (root === null) {
    return [];
  }

  const queue = [root];
  const result = [];
  let index = 0;

  while (index < queue.length) {
    const levelSize = queue.length - index;
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue[index++];

      level.push(node.value);

      if (node.left !== null) {
        queue.push(node.left);
      }

      if (node.right !== null) {
        queue.push(node.right);
      }
    }

    result.push(level);
  }

  return result;
}

console.log(levelOrderByLevel(root));
    
function treeHeight(root) {
  if (root === null) {
    return 0;
  }

  const queue = [root];
  let index = 0;
  let height = 0;

  while (index < queue.length) {
    const levelSize = queue.length - index;

    for (let i = 0; i < levelSize; i++) {
      const node = queue[index++];

      if (node.left !== null) {
        queue.push(node.left);
      }

      if (node.right !== null) {
        queue.push(node.right);
      }
    }

    height++;
  }

  return height;
}

console.log(treeHeight(root));
    
function minDepth(root) {
  if (root === null) {
    return 0;
  }

  const queue = [{ node: root, depth: 1 }];
  let index = 0;

  while (index < queue.length) {
    const { node, depth } = queue[index++];

    if (node.left === null && node.right === null) {
      return depth;
    }

    if (node.left !== null) {
      queue.push({
        node: node.left,
        depth: depth + 1
      });
    }

    if (node.right !== null) {
      queue.push({
        node: node.right,
        depth: depth + 1
      });
    }
  }

  return 0;
}

console.log(minDepth(root));

Pro Tip

Think of level-order traversal as a queue moving through the tree from top to bottom. When a problem asks for the first node, shortest depth, maximum width, or values grouped by levels, breadth-first traversal is often a useful starting point.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.