5.9 Binary Tree Level Order Traversal

5.9.1 Problem Metadata

5.9.2 Description

Given the root of a binary tree, return the level order traversal of its nodes’ values (i.e., from left to right, level by level).

5.9.3 Examples

Example 1: Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Example 2: Input: root = [1] Output: [[1]]

Example 3: Input: root = [] Output: []

5.9.4 Constraints

  • The number of nodes in the tree is in the range [0, 2000]
  • -1000 <= Node.val <= 1000

5.9.5 Solution - BFS with Two Queues

5.9.5.1 Walkthrough

Use level-order traversal while keeping two queues: one for the current level, one for the next.

  1. Seed currentLevelQueue with root.
  2. Pop nodes from the current queue, append their values to the level list, and push their children into nextLevelQueue.
  3. When the current queue empties, swap queues, reset level, and continue; each swap marks a new level in levels.

This separates nodes by depth without tracking counts.

5.9.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n) for queues and result

5.9.5.3 Implementation Steps

  1. Initialize two queues and an empty result list.
  2. While current queue not empty, pop nodes, append values, and enqueue children to the next queue.
  3. When current queue empties, swap queues and start a new level list.

5.9.5.4 Code - Java

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) {
        return levels;
    }

    // Two queues for current level and next level
    Queue<TreeNode> currLvlQ = new LinkedList<>();
    Queue<TreeNode> nextLvlQ = new LinkedList<>();
    // One list for storing current level values
    List<Integer> level = new ArrayList<>();

    // Enqueue root
    currLvlQ.offer(root);

    while (!currLvlQ.isEmpty()) {
        // Dequeue from current level
        TreeNode node = currLvlQ.poll();

        // Add node value to current level list
        level.add(node.val);

        // Enqueue left/right children to next level queue
        if (node.left != null) {
            nextLvlQ.offer(node.left);
        }
        if (node.right != null) {
            nextLvlQ.offer(node.right);
        }

        // Proceed to next level when current queue is empty
        if (currLvlQ.isEmpty()) {
            // Replace currLvlQ with nextLvlQ
            currLvlQ = nextLvlQ;
            nextLvlQ = new LinkedList<>();

            // Add current level to result 2D list
            levels.add(level);

            // Initialize new level list
            level = new ArrayList<>();
        }
    }

    return levels;
}

5.9.5.5 Code - Golang

func levelOrder(root *TreeNode) [][]int {
    levels := make([][]int, 0)

    if root == nil {
        return levels
    }

    // Two queues for current level and next level
    currLvlQ := make([]*TreeNode, 0)
    nextLvlQ := make([]*TreeNode, 0)
    // One list for storing current level values
    level := make([]int, 0)

    // Enqueue root
    currLvlQ = append(currLvlQ, root)

    for len(currLvlQ) != 0 {
        // Dequeue from current level
        node := currLvlQ[0]
        currLvlQ = currLvlQ[1:]

        // Add node value to current level list
        level = append(level, node.Val)

        // Enqueue left/right children to next level queue
        if node.Left != nil {
            nextLvlQ = append(nextLvlQ, node.Left)
        }
        if node.Right != nil {
            nextLvlQ = append(nextLvlQ, node.Right)
        }

        // Proceed to next level when current queue is empty
        if len(currLvlQ) == 0 {
            // Replace currLvlQ with nextLvlQ
            currLvlQ = nextLvlQ
            nextLvlQ = make([]*TreeNode, 0)

            // Add current level to result 2D list
            levels = append(levels, level)

            // Initialize new level list
            level = make([]int, 0)
        }
    }

    return levels
}

5.9.6 Solution - DFS

5.9.6.1 Walkthrough

We could traverse the tree recursively with strategy, and additionally pass current level into recursive method.

5.9.6.2 Analysis

DFS has time complexity of O(n) as every node is visited and thus Auxiliary Space is also O(n).

5.9.6.3 Implementation Steps

dfs 1.3.1

5.9.6.4 Code - DFS

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    traverse(root, 0, ans);

    return ans;
}

private void traverse(TreeNode root, int level, List<List<Integer>> ans) {
    if(root == null){
        return;
    }

    if(ans.size()<=level){
        ans.add(new ArrayList<>());
    }

    ans.get(level).add(root.val);

    traverse(root.left, level + 1, ans);
    traverse(root.right, level + 1, ans);
}