Leetcode - 102. Binary Tree Level Order Traversal

Medium

Feb 18, 2026

#binary-tree

#queue

102. Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

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

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

Constraints:

Notes

Intuition

Level order traversal of binary tree is done with queue, but we need to process all the same level together.

Implementation

Basic level order traversal where we simply want to print the values or do something with each level sequentially is quite simple with a queue, just dequeue process and then push the right and left if they exist. However, in this problem, we want to add all values from a given level to an array and then add that array to the result, therefore, we can't simply store the nodes by individually in the queue. Each queue element should contain all nodes for that level.

The queue will consist of an array of nodes for that level. Start off by initializing the queue with its first element being an array containing just the root (level1). Then, iterate while the queue is not empty, dequeue the nodes from the queue. Initialize a temporary array for the values that will be pushed to the result and another array for the level nodes that will be pushed to the queue after processing the current nodes. Iterate over the nodes, add the value to the temporary array. If the node has left, add that node to the level nodes array, same with right. After this iteration, we add the temporary array to the result and check if the level nodes are not empty and add them to the queue.

Edge-cases

If the root is null, return empty array early.

Time: O(n): we process each node once.
Space: O(n): the queue can contain all the nodes at worst

Complexity

Solution

from typing import List, Optional
from lcutils import TreeNode
from collections import deque

# 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]]:
        result = []
        if not root:
            return result

        q = deque([[root]])
        while q:
            nodes = q.popleft()
            temp = []
            level_nodes = []
            for node in nodes:
                temp.append(node.val)
                if node.left:
                    level_nodes.append(node.left)
                if node.right:
                    level_nodes.append(node.right)
            if level_nodes:
                q.append(level_nodes)
            result.append(temp)

        return result


if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()
    root = TreeNode.create(1,2,3,4,None,None,5)
    print(str(root))
    