102. Binary Tree Level Order Traversal

Summary

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).

Approach

BFS.

Function

Initialization:

nodes = [root]
ans = []

Function: While nodes is not empty: new_nodes = [] values = [] for n in nodes: if n is None: continue append n.val to values if n.left: append n.left to new_nodes if n.right: append n.right to new_nodes nodes = new_nodes if values: append values to ans

Complexity

Time Complexity: O(N) Space Complexity: O(N)

However, this algorithm may be a little slower than another solution. Can we find a simpler one?

Approach

Use pre-order traversal. The algorithm becomes simpler.

Algorithm

Initialization:

ans = defaultdict(list)

Function traverse(root, depth): if root: append root.val to ans[depth] traverse(root.left, depth + 1) traverse(root.right, depth + 1)

Return list(ans.values()). In Python, the dictionary keeps insertion order, which matches depth order here.

Complexity

Time Complexity: O(N) Space Complexity: O(N)

The complexity is the same, but this version avoids keeping a separate list of nodes for each level and uses fewer checks.