Binary Tree Level Order Traversal

Medium · Trees · Explanation and code example

Breadth First Search

How it works

Level order traversal visits a tree level by level, from left to right.
BFS naturally fits this because it processes nodes in the order they appear using a queue.

The idea:

  • Push the root into the queue.
  • Repeatedly remove nodes from the queue, these form the current level.
  • Add their children into the queue, these will form the next level.
  • Continue until the queue is empty.

This ensures every node is visited in perfect level-order.

Steps

  1. If the tree is empty, return an empty list.
  2. Create a queue and push the root.
  3. While the queue is not empty:
    • Let qLen be the number of nodes currently in the queue (these nodes form one full level).
    • Create an empty list level.
    • Repeat qLen times:
      • Pop a node from the queue.
      • Add its value to level.
      • Push its left and right children if they exist.
    • Append level to the result list.
  4. Return the result list containing all levels.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Processing Nodes Individually Instead of by Level

In BFS, you must process all nodes at the current level before moving to the next. A common mistake is to pop nodes one at a time without tracking how many belong to the current level. This causes nodes from different levels to be mixed together in the same output list.

Not Handling the Empty Tree Case

When the root is null, the function should return an empty list. Forgetting this check can lead to null pointer exceptions when attempting to add the root to the queue or access its value.

Python code example

from typing import List, Optional
import collections

# 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

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        q = collections.deque()
        q.append(root)

        while q:
            qLen = len(q)
            level = []
            for i in range(qLen):
                node = q.popleft()
                if node:
                    level.append(node.val)
                    q.append(node.left)
                    q.append(node.right)
            if level:
                res.append(level)

        return res

C++ code example

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

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

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

        while (!q.empty()) {
            vector<int> level;
            int size = q.size();

            for (int i = q.size(); i > 0; i--) {
                TreeNode* node = q.front();
                q.pop();
                if (node) {
                    level.push_back(node->val);
                    q.push(node->left);
                    q.push(node->right);
                }
            }
            if (!level.empty()) {
                res.push_back(level);
            }
        }
        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations