Problem overview
The function levelOrderTraversal receives the root of a binary tree, a *TreeNode, and returns a [][]int: one inner slice per level of the tree, listing that level's values from left to right.
In the example the root is 3, its children are 9 and 20, and the children of 20 are 15 and 7. Level 0 holds [3], level 1 holds [9 20] and level 2 holds [15 7], so the answer is [[3] [9 20] [15 7]].
Approach: carry the level along
The usual way to produce levels is a breadth-first search with a queue. This lesson uses a different idea that needs no queue. A recursive depth-first search visits every node, and each call knows its own level: the root is at level 0 and a child is one level deeper than its parent. Each node can append its value directly to result[level].
Visiting the left child before the right child keeps each level in left-to-right order. Take any two nodes on the same level. The one that is further left belongs to a subtree that the search finishes entirely before it starts on the other, so it appends first.
The only problem is that result[level] may not exist yet. The search goes deep before it goes wide, so the first node it reaches on a new level must create that level's slice. Levels appear one at a time, so a level number is either already present or exactly len(result).
Step by step
- Declare
resultas an empty[][]int.result[level]will hold the values of that level. - Call
levelOrderDfswithroot, level 0 and&result. The pointer lets the helper add new levels to the slice and have the caller see them. - Return
result. - Declare the helper. It takes
root *TreeNode,level intandresult *[][]int, and returns nothing. - Stop at
nil. An empty subtree has no values. - Create the level when needed. If
level == len(*result), this is the first node reached on that level, so append an empty[]int{}to*result. - Append the value to
(*result)[level]and store the result back in the same place. - Recurse into the left child with
level + 1. - Recurse into the right child with
level + 1.
The solution in Go
func levelOrderTraversal(root *TreeNode) [][]int {
result := [][]int{}
levelOrderDfs(root, 0, &result)
return result
}
func levelOrderDfs(root *TreeNode, level int, result *[][]int) {
if root == nil {
return
}
if level == len(*result) {
*result = append(*result, []int{})
}
(*result)[level] = append((*result)[level], root.Val)
levelOrderDfs(root.Left, level+1, result)
levelOrderDfs(root.Right, level+1, result)
}
The Go details worth a closer look:
- Pointer to a slice of slices. Adding a level changes the length of the outer slice, and
appendreturns the grown slice rather than changing its argument. A function that received a plain[][]intwould append to its own copy of the slice header, and the caller would never see the new levels. With*[][]intthere is one slice header, owned bylevelOrderTraversal, and every call updates it. - The parentheses in
(*result)[level]. Indexing binds more tightly than the*operator, so*result[level]means "index the pointer, then dereference", and indexing a pointer to a slice doesn't compile. The parentheses dereference first and then index. - Appending to an inner slice.
(*result)[level]is an element of the outer slice, and it can be assigned to like a variable. Appending to the inner slice may give it a new backing array, and the assignment stores the new header in the outer slice. - Why equality is enough. A node at level
Lis reached only through its parent at levelL - 1, which already created levelL - 1. Solevelis never more thanlen(*result), and testing==covers the "level is missing" case. - Empty slices, not
nil.[][]int{}and[]int{}are empty but notnil. For an empty tree the function returns a slice of length 0, which prints as[].
Complexity
Time: O(n) for n nodes. Every node is visited once and does a constant amount of work, plus one extra call for each missing child. The appends are amortised constant time.
Space: O(n) for the result, which holds every value once. The recursion adds O(h) stack frames, where h is the height of the tree: close to log n for a balanced tree and n for a tree that is a single chain. A queue-based search would use O(w) extra space, where w is the widest level, but it needs the queue code.
Edge cases and common mistakes
- An empty tree. The helper returns immediately and the function returns
[], not a slice holding one empty level. - A chain of nodes. A tree where each node has only a right child gives one value per level:
[[1] [2] [3]]for the chain 1, 2, 3. - Visiting the right child first. Every level then comes out in right-to-left order. For the example, the second level would be
[20 9]. - Using
level > len(*result). That condition never holds, so no level would ever be created and the next line would fail with an index out of range panic. - Using
if level >= len(*result). This works, but only because levels appear one at a time. With==the code states the invariant it relies on. - Forgetting
level+1. If the children are passed the samelevelas the parent, all values land inresult[0]. - Dropping the assignment on the
append. Go refuses to compile a bareappendcall, but writing it into a throwaway variable would silently lose the values.
Testing
- The tree with root 3, children 9 and 20, and grandchildren 15 and 7 under 20 gives
[[3] [9 20] [15 7]]. - A single node with value 1 gives
[[1]]. - An empty tree gives
[]. - A root 1 with only a left child 2 gives
[[1] [2]].