102. Binary Tree Level Order Traversal - Explanation

Problem Link

Description

Given a binary tree root, return the level order traversal of it as a nested list, where each sublist contains the values of nodes at a particular level in the tree, from left to right.

Example 1:

Input: root = [1,2,3,4,5,6,7]

Output: [[1],[2,3],[4,5,6,7]]

Example 2:

Input: root = [1]

Output: [[1]]

Example 3:

Input: root = []

Output: []

Constraints:

• 0 <= The number of nodes in the tree <= 1000.
• -1000 <= Node.val <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.

Hint 1

The level of a tree refers to the nodes that are at equal distance from the root node. Can you think of an algorithm that traverses the tree level by level, rather than going deeper into the tree?

Hint 2

We can use the Breadth First Search (BFS) algorithm to traverse the tree level by level. BFS uses a queue data structure to achieve this. At each step of BFS, we only iterate over the queue up to its size at that step. Then, we take the left and right child pointers and add them to the queue. This allows us to explore all paths simultaneously.

Hint 3

The number of times we iterate the queue corresponds to the number of levels in the tree. At each step, we pop all nodes from the queue for the current level and add them collectively to the resultant array. This ensures that we capture all nodes at each level of the tree.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Depth First Search

Intuition

Level order traversal means visiting the tree level by level, from top to bottom.
With DFS, instead of using a queue, we use recursion and pass the current depth.
Each time we reach a node:

• If this is the first time visiting this depth, create a new list for that level.
• Add the node's value to the list for that depth.
• Recursively explore left and right children with depth + 1.

Algorithm

1. Maintain an empty list res where res[d] stores all nodes at depth d.
2. Define a recursive function dfs(node, depth):
   • If node is null, return.
   • If res has no list for this depth, append a new empty list.
   • Append the node's value to res[depth].
   • Recurse on node.left with depth + 1.
   • Recurse on node.right with depth + 1.
3. Call dfs(root, 0).
4. Return res.

# 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 = []

        def dfs(node, depth):
            if not node:
                return None
            if len(res) == depth:
                res.append([])

            res[depth].append(node.val)
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return res

Time & Space Complexity

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

---

2. Breadth First Search

Intuition

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.

Algorithm

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.

# 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

Time & Space Complexity

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

---

Common Pitfalls

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.