Level Order Traversal

Return the values of a binary tree level by level from top to bottom using a queue.

binary-tree queue bfs traversal

Write a function `level_order_traversal(root)` that performs a level order traversal (breadth-first search) on a binary tree and returns a list of lists, where each inner list contains the values of the nodes at that level, from left to right. Levels are ordered from top to bottom.

The binary tree nodes are defined as:

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
```

The input `root` is either a `TreeNode` instance or `None` for an empty tree. In the test harness, the tree is also serialized as nested dictionaries: `{"val": 3, "left": ..., "right": ...}`. Your solution must handle both `TreeNode` objects and dictionary-based representations. Node values can be any integers (including negative and zero).

Your function must return a list of lists. For an empty tree, return `[]`.

Examples:
```
Input tree: [3, 9, 20, None, None, 15, 7]
     3
    / \
   9  20
      /  \
     15   7
Output: [[3], [9, 20], [15, 7]]
```

```
Input tree: [1, 2, 3, 4, None, None, 5]
     1
    / \
   2   3
  /     \
 4       5
Output: [[1], [2, 3], [4, 5]]
```

You may assume the `TreeNode` class is already defined in the starter code. Do not modify the class definition.

Constraints

Tree node count: 0 <= n <= 1000
Node values: -1000 <= val <= 1000
The tree is not necessarily balanced.
The implementation should run in O(n) time and O(n) space.

Example

# Example 1
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(level_order_traversal(root))  # [[3], [9, 20], [15, 7]]

# Example 2
empty_root = None
print(level_order_traversal(empty_root))  # []

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a queue (e.g., collections.deque) to process nodes in breadth-first order.

To read the value of a node, you can use: `node["val"] if isinstance(node, dict) else node.val`

Process nodes level by level: for each level, dequeue all nodes currently in the queue, record their values, and enqueue their children.

If the root is None, return an empty list immediately.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.