LeetCode 102: Binary Tree Level Order Traversal — Step-by-Step Visual Trace

#leetcode #python #algorithms #datastructures

Medium — Binary Tree | BFS | Queue | Level Order

The Problem

Given the root of a binary tree, return the level order traversal of its nodes' values as a list of lists, where each inner list contains all node values at that level from left to right.

Approach

Use a breadth-first search (BFS) approach with a queue to process nodes level by level. For each level, extract all current nodes, collect their values, and add their children to the next level queue.

Time: O(n) · Space: O(w)

Code

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = [root]

        while queue:
            level = []
            next_level = []

            for node in queue:
                level.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)

            result.append(level)
            queue = next_level

        return result