Binary Tree Level Order Traversal

Given a binary tree, return its level order traversal where the nodes in each level are ordered from left to right.

Example(s)

Example 1:

Input:
    4
   / \
  2   7

Output: [[4], [2, 7]]
Explanation:
Level 0: [4]
Level 1: [2, 7]

Example 2:

Input:
    2
   / \
  10  15
        \
         20

Output: [[2], [10, 15], [20]]
Explanation:
Level 0: [2]
Level 1: [10, 15]
Level 2: [20]

Example 3:

Input:
    1
   / \
  9   32
 /      \
3        78

Output: [[1], [9, 32], [3, 78]]
Explanation:
Level 0: [1]
Level 1: [9, 32]
Level 2: [3, 78]

Example 4:

Input:
    1

Output: [[1]]
Explanation:
Only root node, one level.

Solution

The solution uses BFS (Breadth-First Search) with a queue:

Use queue: Process nodes level by level
Level processing: Process all nodes at current level before moving to next
Collect values: Add node values to current level array
Add children: Add children to queue for next level

JavaScript Solution
Python Solution

JavaScript Solution - BFS

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/

/**
* Level order traversal
* @param {TreeNode} root - Root of binary tree
* @return {number[][]} - Level order traversal
*/
function levelOrder(root) {
if (!root) return [];

const result = [];
const queue = [root];

while (queue.length > 0) {
  const levelSize = queue.length;
  const currentLevel = [];
  
  // Process all nodes at current level
  for (let i = 0; i < levelSize; i++) {
    const node = queue.shift();
    currentLevel.push(node.val);
    
    // Add children to queue for next level
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  result.push(currentLevel);
}

return result;
}

// Helper function to create tree nodes for testing
function TreeNode(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}

// Test cases
// Example 1: [4, 2, 7]
const tree1 = new TreeNode(4,
new TreeNode(2),
new TreeNode(7)
);
console.log('Example 1:', levelOrder(tree1)); // [[4], [2, 7]]

// Example 2: [2, 10, 15, null, null, null, 20]
const tree2 = new TreeNode(2,
new TreeNode(10),
new TreeNode(15, null, new TreeNode(20))
);
console.log('Example 2:', levelOrder(tree2)); // [[2], [10, 15], [20]]

// Example 3: [1, 9, 32, 3, null, null, 78]
const tree3 = new TreeNode(1,
new TreeNode(9, new TreeNode(3)),
new TreeNode(32, null, new TreeNode(78))
);
console.log('Example 3:', levelOrder(tree3)); // [[1], [9, 32], [3, 78]]

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional
from collections import deque

def level_order(root: Optional[TreeNode]) -> List[List[int]]:
  """
  Level order traversal
  
  Args:
      root: Root of binary tree
      
  Returns:
      List[List[int]]: Level order traversal
  """
  if not root:
      return []
  
  result = []
  queue = deque([root])
  
  while queue:
      level_size = len(queue)
      current_level = []
      
      # Process all nodes at current level
      for _ in range(level_size):
          node = queue.popleft()
          current_level.append(node.val)
          
          # Add children to queue for next level
          if node.left:
              queue.append(node.left)
          if node.right:
              queue.append(node.right)
      
      result.append(current_level)
  
  return result

# Helper class for testing
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

# Test cases
# Example 1: [4, 2, 7]
tree1 = TreeNode(4,
  TreeNode(2),
  TreeNode(7)
)
print('Example 1:', level_order(tree1))  # [[4], [2, 7]]

# Example 2: [2, 10, 15, None, None, None, 20]
tree2 = TreeNode(2,
  TreeNode(10),
  TreeNode(15, None, TreeNode(20))
)
print('Example 2:', level_order(tree2))  # [[2], [10, 15], [20]]

# Example 3: [1, 9, 32, 3, None, None, 78]
tree3 = TreeNode(1,
  TreeNode(9, TreeNode(3)),
  TreeNode(32, None, TreeNode(78))
)
print('Example 3:', level_order(tree3))  # [[1], [9, 32], [3, 78]]

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (DFS with Level Tracking)

Here's an alternative using DFS that tracks the level:

JavaScript DFS
Python DFS

/**
 * Alternative: DFS with level tracking
 */
function levelOrderDFS(root) {
  const result = [];
  
  function dfs(node, level) {
    if (!node) return;
    
    // Create level array if needed
    if (result.length === level) {
      result.push([]);
    }
    
    // Add node to its level
    result[level].push(node.val);
    
    // Recursively process children (next level)
    dfs(node.left, level + 1);
    dfs(node.right, level + 1);
  }
  
  dfs(root, 0);
  return result;
}

def level_order_dfs(root: Optional[TreeNode]) -> List[List[int]]:
    """
    Alternative: DFS with level tracking
    """
    result = []
    
    def dfs(node: Optional[TreeNode], level: int):
        if not node:
            return
        
        # Create level array if needed
        if len(result) == level:
            result.append([])
        
        # Add node to its level
        result[level].append(node.val)
        
        # Recursively process children (next level)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    
    dfs(root, 0)
    return result

Complexity

Time Complexity: O(n) - Where n is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(n) - For the queue (in worst case, all nodes at the last level). Also O(n) for the result array.

Approach

The solution uses BFS (Breadth-First Search) with a queue:

Initialize queue:
- Start with root node in queue
- Queue will contain nodes to process
Level-by-level processing:
- For each level:
  - Get current level size (number of nodes at this level)
  - Process all nodes at current level
  - Collect their values into current level array
  - Add their children to queue for next level
Queue operations:
- Dequeue nodes from front (current level)
- Enqueue children to back (next level)
- This ensures level-by-level processing
Result building:
- After processing each level, add level array to result
- Continue until queue is empty

Key Insights

BFS with queue: Natural for level-order traversal
Level size tracking: Process all nodes at current level before next
Left-to-right order: Process left child before right child
O(n) time: Visit each node once
O(n) space: Queue and result array

Step-by-Step Example

Let's trace through Example 1:

Tree:
    4
   / \
  2   7

Initialization:
  queue = [4]
  result = []

Iteration 1 (Level 0):
  levelSize = 1
  currentLevel = []
  
  Process node 4:
    currentLevel.push(4) → [4]
    Add children: queue.push(2), queue.push(7)
    queue = [2, 7]
  
  result.push([4]) → [[4]]

Iteration 2 (Level 1):
  levelSize = 2
  currentLevel = []
  
  Process node 2:
    currentLevel.push(2) → [2]
    No children
    queue = [7]
  
  Process node 7:
    currentLevel.push(7) → [2, 7]
    No children
    queue = []
  
  result.push([2, 7]) → [[4], [2, 7]]

Queue is empty, done.

Result: [[4], [2, 7]]

Visual Representation

Example 1:
    4
   / \
  2   7

BFS traversal:
  Level 0: [4]
    Queue: [4]
    Process: 4
    Queue: [2, 7]
  
  Level 1: [2, 7]
    Queue: [2, 7]
    Process: 2, 7
    Queue: []
  
  Result: [[4], [2, 7]]

Example 2:
    2
   / \
  10  15
        \
         20

BFS traversal:
  Level 0: [2]
    Queue: [2]
    Process: 2
    Queue: [10, 15]
  
  Level 1: [10, 15]
    Queue: [10, 15]
    Process: 10, 15
    Queue: [20]
  
  Level 2: [20]
    Queue: [20]
    Process: 20
    Queue: []
  
  Result: [[2], [10, 15], [20]]

Edge Cases

Empty tree: Return [] (no levels)
Single node: Return [[val]] (one level)
Skewed tree: Still works correctly
Complete tree: All levels are full
Unbalanced tree: Some levels have fewer nodes

Important Notes

Level order: Process nodes level by level
Left to right: Process left child before right child
Queue-based: BFS naturally processes level by level
O(n) time: Visit each node once
O(n) space: Queue and result array

Why BFS Works

Key insight:

Level order traversal requires processing nodes level by level
BFS with a queue naturally processes nodes in this order
Queue ensures we process all nodes at level i before level i+1
This is exactly what we need for level order traversal

Queue property:

FIFO (First In First Out) ensures level-by-level processing
Nodes at level i are added before nodes at level i+1
When we process level i, all nodes at level i+1 are in queue

Binary Tree Level Order Traversal II: Reverse level order
Average of Levels in Binary Tree: Calculate averages per level
Binary Tree Zigzag Level Order Traversal: Zigzag pattern
N-ary Tree Level Order Traversal: Similar for N-ary tree

Takeaways

BFS with queue is natural for level order
Level size tracking ensures we process one level at a time
O(n) time to visit all nodes
O(n) space for queue and result
Classic tree problem with practical applications

Example(s)​

Solution​

JavaScript Solution - BFS

Output:

Python Solution - BFS

Output:

Alternative Solution (DFS with Level Tracking)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Why BFS Works​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (DFS with Level Tracking)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Why BFS Works

Related Problems

Takeaways