Binary Tree Level Order Traversal

Medium

The problem

Return the values of the tree grouped by level: first the root, then its children from left to right, then the next row, and so on. The result is a list of lists, one per level.

Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]
Example 2
Input: root = [1]
Output: [[1]]
Example 3
Input: root = []
Output: []

Limits

0 ≤ number of nodes ≤ 2,000
-1000 ≤ node value ≤ 1000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Visit nodes row by row. What data structure hands you nodes in the order they were discovered?

The idea

BFS with a queue; each round process exactly len(queue) nodes — that is one level.

Target: O(n) time, O(w) space

Go function shape

func levelOrder(root *TreeNode) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// LevelOrder: BFS with a queue, one level per outer iteration.
func LevelOrder(root *TreeNode) [][]int {
	res := [][]int{}
	if root == nil {
		return res
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue) // freeze: exactly these nodes belong to this level
		level := make([]int, 0, size)
		for i := 0; i < size; i++ {
			n := queue[0]
			queue = queue[1:]
			level = append(level, n.Val)
			if n.Left != nil {
				queue = append(queue, n.Left)
			}
			if n.Right != nil {
				queue = append(queue, n.Right)
			}
		}
		res = append(res, level)
	}
	return res
}

Read the lesson: Trees: BFS / DFS