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

Constraints:

The number of nodes in the tree is in the range [0, 2000].

-1000 <= Node.val <= 1000

While this is technically a tree problem, it is actually a graph problem in disguise! Think about what level order traversal is asking us to do:

Starting from the root, count its children from left to right.
Starting from the first child counted, start counting its children. Then repeat for the second child counted, etc. In other words, we count from the root in order of nodes we first see. This is exactly what BFS does!

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
	
	queue = [root]
	while queue:
		...
		for node in queue:
			...
			# add children to queue

There are a few tricky things we have to consider before we get the full solution.

We want to avoid adding empty nodes to the queue. Thus, if root is empty we should immediately return an empty list; similarly, we should avoid adding empty children.
We have to somehow track each level as one list, so we cannot enqueue all the children encountered before we have finished processing all nodes in a given level. The simplest way to do this is to track how many nodes are in each level, and pop only that many nodes off the BFS queue.

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
	from collections import deque
	
	if root is None:
		return []
	
	ans = []
	queue = deque([root])
	while queue:
		level = []
		
		# only process nodes of this level
		# when len(queue) is evaluated, the queue only contains all nodes 
		# of some level, and no other levels.
		for _ in range(len(queue)):
			node = queue.popleft()
			level.append(node.val)
			
			# only process non-empty nodes
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		
		ans.append(level)
	
	return ans

Time Complexity

Notice that since this is a tree, the BFS runtime simplifies to $\mathcal{O}(V) = \mathcal{O}(n)$ . This is not changed further since the processing time at each node remains constant time, and all other operations are also constant time.

Space Complexity

Since we are dealing with binary trees, each node has at most 2 children. That means that in the worst case, each level has $2^d$ nodes where $d$ is the current depth. Therefore, our space complexity is $\mathcal{O}(2^d)$ .

However, this can be simplified. The worst case occurs at the lowest level of our binary tree, where there are $2^h$ nodes where $h$ is the height. But think about the number of nodes above it:

1 + 2 + \dotsb + 2^{h-1} = 2^h - 1

This means that $n = 2 (2^h) + 1$ , so $2^h = \frac{n}{2} - 1$ . This means that our space complexity is in fact $\mathcal{O}(n)$ !