Binary Tree Level Order Traversal

Ishaan S Published 24 Oct, 2026

Given the root of a binary tree, return its node values grouped by depth: first a list with the root's value, then a list with the values on the next level, and so on down to the deepest level. Within each level, list the values from left to right.

If the tree is empty, return an empty list.

Trees are written in level order, with null marking a missing child. For example, [5,2,8,null,4,7] is a root 5 whose left child 2 has only a right child 4, and whose right child 8 has a left child 7.

Example 1

Input: root = [5,2,8,null,4,7] Output: [[5],[2,8],[4,7]] Why: Depth 0 holds 5, depth 1 holds 2 and 8, and depth 2 holds 4 (under 2) and 7 (under 8).

Example 2

Input: root = [1] Output: [[1]] Why: A tree with one node has a single level.

Example 3

Input: root = [] Output: [] Why: An empty tree has no levels at all.

Constraints

The number of nodes is between 0 and 2000.
-1000 <= Node.val <= 1000

Pattern Path · Trees: BFS · problem 92 of 169

Which traversal visits nodes in order of their distance from the root?

Breadth-first search with a queue visits nodes level by level. The difficulty is knowing where one level ends and the next begins.

At the start of each round, the queue contains exactly one full level. Record its length, pop that many nodes into a list, and push their children for the next round.

Target: O(n) time, O(w), w = maximum width of the tree (O(n) worst case) extra space.

Start simple

Compute each node's depth with DFS and bucket values by depth (also O(n)); a naive version that re-walks the tree once per level costs O(n · h).

The key idea

Breadth-first search explores nodes in order of their distance from the root, which is exactly the grouping we want. Use a queue and process it one level at a time.

The invariant is: at the start of each round, the queue holds every node of the current level, in left-to-right order, and nothing else. So read size = len(queue), pop exactly size nodes, append their values to a new list, and push each popped node's left child and then right child. The children pushed this round form the next level, still in left-to-right order because parents were processed left to right and each pushes left before right.

When the queue is empty, every level has been emitted. Each node is pushed and popped once, so the time is linear, and the queue never holds more than the widest level.

A DFS that carries the depth and appends into levels[depth] also works, since a preorder walk meets each level's nodes left to right.

Complexity

Time: O(n)
Space: O(w), w = maximum width of the tree (O(n) worst case)

Python

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        levels = []
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):  # exactly the nodes of this level
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            levels.append(level)
        return levels

JavaScript

var levelOrder = function(root) {
  if (root === null) return [];
  const levels = [];
  let queue = [root];
  while (queue.length > 0) {
    const level = [];
    const next = [];
    for (const node of queue) {
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    levels.push(level);
    queue = next; // the children form the next level
  }
  return levels;
};

What the interviewer is checking

It checks that you know BFS cold and can separate levels cleanly, which is the template for many follow-ups (right side view, zigzag order, level averages).

Mistakes to avoid

Using len(queue) inside the loop condition while also pushing children, which mixes two levels together.
Forgetting the empty tree and returning [[]] instead of [].
Popping from the front of a Python list (pop(0)), which is O(n); use collections.deque.

Follow-ups to expect

Return the levels bottom-up instead? (Reverse the result at the end.)
Alternate left-to-right and right-to-left per level? (Reverse every other level.)
Return only the rightmost value per level? (Last node of each round.)

In real software

Org-chart and file-system browsers show items by depth, and web crawlers and social-network "degrees of separation" features process nodes level by level with the same queue technique.

Practice next

import java.util.*;

/** Definition for a binary tree node. */
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        return new ArrayList<>();
    }
}

public class Main {
    // Builds a tree from a level-order array (null = missing child).
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < a.length) {
            TreeNode n = q.poll();
            if (i < a.length && a[i] != null) { n.left = new TreeNode(a[i]); q.add(n.left); }
            i++;
            if (i < a.length && a[i] != null) { n.right = new TreeNode(a[i]); q.add(n.right); }
            i++;
        }
        return root;
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{5, 2, 8, null, 4, 7});
        System.out.println(new Solution().levelOrder(root)); // [[5], [2, 8], [4, 7]]
    }
}

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        return {};
    }
};

// Builds a tree from a level-order array (nullopt = missing child).
TreeNode* build(const vector<optional<int>>& a) {
    if (a.empty() || !a[0]) return nullptr;
    TreeNode* root = new TreeNode(*a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < a.size()) {
        TreeNode* n = q.front(); q.pop();
        if (i < a.size() && a[i]) { n->left = new TreeNode(*a[i]); q.push(n->left); }
        i++;
        if (i < a.size() && a[i]) { n->right = new TreeNode(*a[i]); q.push(n->right); }
        i++;
    }
    return root;
}

int main() {
    TreeNode* root = build({5, 2, 8, nullopt, 4, 7});
    for (auto& level : Solution().levelOrder(root)) {
        cout << '[';
        for (int x : level) cout << x << ' ';
        cout << "] ";
    }
    // [5 ] [2 8 ] [4 7 ]
}

Topics #092 #t-tree-bfs BFS Medium Practice Queue Tree