LeetCode Solutions Blog

Binary Tree Level Order Traversal

Number: 102

Difficulty: Medium

Paid? No

Problem Description

Given the root of a binary tree, return the level order traversal of its nodes' values. In other words, traverse the tree level by level from left to right.

Key Insights

Use Breadth-First Search (BFS) to traverse the tree.
A queue data structure is ideal for maintaining the order of nodes at each level.
For every level, process all nodes currently in the queue and add their children for the next level.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, because each node is processed once.
Space Complexity: O(n), which accounts for the space used by the queue in the worst-case scenario.

Solution

This solution leverages a BFS approach using a queue. The algorithm starts by enqueuing the root node. Then, it enters a loop that continues until the queue is empty. For each iteration—representing one level of the tree—it computes the number of nodes at that level (levelSize), processes these nodes by dequeuing them, and collects their values. Their non-null children are then enqueued. The list of values for each level is added to the final result list. Key data structures include the queue (for managing nodes) and a list (to store level values).

Code Solutions

# 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

from collections import deque

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        # Return an empty list if the tree is empty.
        if not root:
            return []
        
        result = []  # Final result list containing values of each level.
        queue = deque([root])  # Initialize the queue with the root node.
        
        # Process nodes level by level.
        while queue:
            level_size = len(queue)  # Number of nodes at the current level.
            level_nodes = []  # List to hold node values at the current level.
            
            for _ in range(level_size):
                node = queue.popleft()  # Dequeue the next node.
                level_nodes.append(node.val)
                # Enqueue left child if it exists.
                if node.left:
                    queue.append(node.left)
                # Enqueue right child if it exists.
                if node.right:
                    queue.append(node.right)
            # Append the current level's values to the result.
            result.append(level_nodes)
        return result