Binary Tree Level Order Traversal

Problem 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).

Examples

Constraints

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

Draining Queue Elements Level by Level

Breadth-first search naturally visits nodes in order of their distance from the root. However, a standard BFS queue flat-maps all nodes, losing track of which level they belong to.

To group nodes by level, we must slice the queue iteration. At the beginning of each level loop, record the queue size N. This size dictates exactly how many nodes belong to the current level. We then pop and process exactly N elements, adding their values to a temporary list and pushing their children to the back of the queue. Once N elements are consumed, the level is complete, and we append the list to our output.

Solution 1: Iterative Queue BFS

Use a queue to track nodes, using a nested loop bounded by the snapshot of the queue size to group levels.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // snapshot size for current level
            List<Integer> levelList = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode curr = queue.poll();
                levelList.add(curr.val);

                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
            result.add(levelList);
        }
        return result;
    }
}

from collections import deque


class Solution:
    def levelOrder(self, root: TreeNode) -> list[list[int]]:
        result = []
        if not root:
            return result

        queue = deque([root])

        while queue:
            level_size = len(queue)  # snapshot size for current level
            level_list = []

            for _ in range(level_size):
                curr = queue.popleft()
                level_list.append(curr.val)

                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)

            result.append(level_list)

        return result

#include <vector>
#include <queue>

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> result;
        if (!root) return result;

        std::queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size(); // snapshot size for current level
            std::vector<int> levelList;

            for (int i = 0; i < levelSize; i++) {
                TreeNode* curr = q.front();
                q.pop();
                levelList.push_back(curr->val);

                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
            result.push_back(levelList);
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Every node is processed once.
• Space Complexity: O(w) where w is the maximum tree width, representing the peak queue size. In the worst case (full binary tree), this is O(n/2) = O(n).

Where it breaks: Nothing breaks for standard use cases. If the tree is extremely wide and contains millions of nodes, the queue memory usage can become a bottleneck.

Common Mistakes

• Not taking a snapshot of queue size. If you write for (int i = 0; i < queue.size(); i++), the loop condition will evaluate the dynamically growing queue size as you insert child nodes, mixing levels together.
• Not handling the empty tree case. If root == null, the queue should not be initialized or polled, otherwise you will get null pointer exceptions.
• Pushing null nodes to the queue. Always check if curr.left or curr.right is non-null before offering them to the queue to avoid polluting the level lists with null values.

Frequently Asked Questions

Can this be solved recursively? Yes. You can perform a Depth-First Search (DFS) and pass the current node depth as an argument. You then append the node value to the sub-list at index depth in the results list, initializing new lists as the depth increases. This achieves the same result but uses recursion.

How does this differ from zigzag level order traversal? Zigzag traversal (LeetCode 103) reverses the order of elements for every other level. The level-by-level queue mechanics are identical, but you append elements either forward or backward depending on the level index parity.

What does this problem test in interviews? It tests your basic competency with queue-based Breadth-First Search (BFS) and your ability to group streaming data using snapshot size boundaries.

← All Problems