102. Binary Tree Level Order Traversal

Problem Link

Level order traversal requires visiting nodes level by level, from top to bottom and left to right. This naturally suggests using a queue, since queues process elements in the same order they are added.

We start by placing the root node into the queue. Each iteration of the outer loop represents processing one full level of the tree. At the beginning of each level, we record the current size of the queue, which tells us how many nodes belong to that level.

We then process exactly that many nodes:

• Remove a node from the queue.
• Add its value to the current level list.
• Push its left and right children into the queue for processing in the next level.

Null nodes are skipped to avoid unnecessary work. After processing all nodes of the current level, if the level contains any values, we append it to the final result. This continues until the queue is empty, meaning all levels have been traversed.

Runtime Complexity

Time: \(O(n)\), where \(n\) is the number of nodes in the tree

Space: \(O(n)\), for the queue used during traversal

PythonGo

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        levels = []
        q = deque([root])
        while q:
            level = []
            for _ in range(len(q)):
                node = q.pop()
                if not node:
                    continue
                level.append(node.val)
                q.appendleft(node.left)
                q.appendleft(node.right)
            if level:
                levels.append(level)
        return levels

func levelOrder(root *TreeNode) [][]int {
    queue := make(chan *TreeNode, 2000)
    queue <- root
    var levels [][]int
    var level []int
    var node *TreeNode
    var size int
    for len(queue) > 0 {
        level = make([]int, 0)
        size = len(queue)
        for i := 0; i < size; i++ {
            node = <-queue
            if node == nil {
                continue
            }
            level = append(level, node.Val)
            queue <- node.Left
            queue <- node.Right
        }
        if len(level) > 0 {
            levels = append(levels, level)
        }
    }
    return levels
}

---