Binary Tree Level Order Traversal

medium
TreesTreeBinary TreeBreadth-First Search

Given the root of a binary tree, return the level order traversal of its nodes' values, where each level is grouped as a separate list from left to right.

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: []

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

BFS with Queue

Intuition

Level order traversal is the textbook application of breadth-first search. We use a queue to process nodes level by level. The key technique is to record the size of the queue at the start of each level -- this tells us exactly how many nodes belong to the current level. We dequeue that many nodes, collect their values, and enqueue their children for the next level. This continues until the queue is empty.

Algorithm

  1. If the root is null, return an empty list.
  2. Initialize a queue with the root and an empty result list.
  3. While the queue is not empty, record its current size as the level size.
  4. Create a list for the current level.
  5. Dequeue exactly levelSize nodes, adding each value to the current level list.
  6. For each dequeued node, enqueue its non-null left and right children.
  7. Add the current level list to the result.
  8. Return the result.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};
Java 21
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 size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}
Python 3.12
from collections import deque


def levelOrder(root: Optional[TreeNode]) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result
Go 1.26
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    var result [][]int
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue)
        level := make([]int, 0, size)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, level)
    }
    return result
}
Approach 2

Recursive DFS

Intuition

Although level order traversal is naturally a BFS problem, we can also solve it with DFS by passing the current depth as a parameter. When we visit a node at a given depth, we add its value to the corresponding list in our result. If the result list does not yet have an entry for this depth, we create a new list. By processing nodes in a pre-order traversal (node, left, right), values at each level are added left-to-right, producing the correct level order.

Algorithm

  1. Create an empty result list.
  2. Define a recursive helper that takes a node and its depth.
  3. If the node is null, return.
  4. If the result list has no entry at this depth, add a new empty list.
  5. Append the node's value to the list at position depth.
  6. Recurse on the left child with depth + 1.
  7. Recurse on the right child with depth + 1.
  8. Call the helper with root and depth 0, then return the result.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        dfs(root, 0, result);
        return result;
    }

private:
    void dfs(TreeNode* node, int depth, vector<vector<int>>& result) {
        if (node == nullptr) return;
        if (depth == result.size()) {
            result.push_back({});
        }
        result[depth].push_back(node->val);
        dfs(node->left, depth + 1, result);
        dfs(node->right, depth + 1, result);
    }
};
Java 21
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
        if (node == null) return;
        if (depth == result.size()) {
            result.add(new ArrayList<>());
        }
        result.get(depth).add(node.val);
        dfs(node.left, depth + 1, result);
        dfs(node.right, depth + 1, result);
    }
}
Python 3.12
def levelOrder(root: Optional[TreeNode]) -> list[list[int]]:
    result = []

    def dfs(node, depth):
        if not node:
            return
        if depth == len(result):
            result.append([])
        result[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    dfs(root, 0)
    return result
Go 1.26
func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, depth int) {
        if node == nil {
            return
        }
        if depth == len(result) {
            result = append(result, []int{})
        }
        result[depth] = append(result[depth], node.Val)
        dfs(node.Left, depth+1)
        dfs(node.Right, depth+1)
    }
    dfs(root, 0)
    return result
}

Frequently asked questions

What is the optimal time complexity of Binary Tree Level Order Traversal?

The most efficient approach in this guide ("Recursive DFS") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Binary Tree Level Order Traversal use?

Binary Tree Level Order Traversal is a medium-level Trees problem involving Tree, Binary Tree, Breadth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Binary Tree Level Order Traversal be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
root=
[3,9,20,null,null,15,7]
Expected Output
[[3],[9,20],[15,7]]