Problem overview
The function zigzagTraversal receives the root of a binary tree, a *TreeNode with fields Val, Left and Right. It returns the node values level by level as a [][]int. The first level, the root, is read left to right, the next one right to left, the next one left to right again, and so on.
For the tree with root 3, children 9 and 20, and 20's children 15 and 7, the answer is [[3], [20, 9], [15, 7]]. Level 0 is [3]. Level 1 holds 9 and 20 left to right, so it is written reversed as [20, 9]. Level 2 holds 15 and 7 and is read left to right.
Approach: collect levels left to right, then flip the odd ones
The usual way to get the levels of a tree is a breadth-first search with a queue. This lesson uses a depth-first search instead, with a small trick: if the search always visits the left child before the right child, then the values of each level are appended to that level's list in left-to-right order, even though the search goes deep first. The first node on level 2 that the search reaches is the leftmost one, the next one it reaches is the one after it, and so on.
So the plan has two parts:
- Run a recursive
dfs(root, level, result)that appends each node's value toresult[level], creating the list for a level the first time the search reaches it. - Walk through the odd levels (1, 3, 5, ...) and reverse each list in place. Level 0 and the other even levels stay as they are.
This separates the two concerns cleanly: the search only has to care about levels, and the zigzag is a simple post-processing step.
Step by step
- Prepare the result and start the search. In
zigzagTraversal,result := [][]int{}is an empty slice of rows. Calldfs(root, 0, &result). The root is on level 0, and the search receives the address ofresult, for a reason explained below. - Flip the odd levels. A
forloop withlevelstarting at 1 andlevel += 2whilelevel < len(result)callsreverse(result[level])on each odd level. - Return
result. - Declare
dfs. It takes the node, its level and a pointer to the result, and returns nothing. - Stop at a missing node. If
root == nil, return. Calls on missing children end here, so this is the base case. - Make sure the level has a row. If
level >= len(*result), append a new empty[]int{}and store the grown slice back through the pointer. Because the search goes down one level at a time, a level is never more than one past the last row. - Append the value to its row.
(*result)[level] = append((*result)[level], root.Val). The assignment is needed becauseappendcan return a new slice. - Recurse into the left subtree with
level+1. - Recurse into the right subtree the same way. Left before right is what keeps every row in left-to-right order.
- Declare
reverse. It takes one row and swaps its elements in place, so it has no return value. - Set up two indexes.
i, j := 0, len(row)-1in theforheader, running whilei < j, and updated with the parallel assignmenti, j = i+1, j-1. - Swap.
row[i], row[j] = row[j], row[i].
The solution in Go
func zigzagTraversal(root *TreeNode) [][]int {
result := [][]int{}
dfs(root, 0, &result)
for level := 1; level < len(result); level += 2 {
reverse(result[level])
}
return result
}
func dfs(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)
dfs(root.Left, level+1, result)
dfs(root.Right, level+1, result)
}
func reverse(row []int) {
for i, j := 0, len(row)-1; i < j; i, j = i+1, j-1 {
row[i], row[j] = row[j], row[i]
}
}
The Go details worth knowing:
- Why
resultis a pointer.appendmay allocate a new backing array when the slice is full and returns the updated slice. A function that receives the slice by value can append to its own copy only, and the caller never sees the new length. Passing*[][]intletsdfswrite the grown slice back:
func addCopy(rows [][]int) {
rows = append(rows, []int{1})
}
func addPtr(rows *[][]int) {
*rows = append(*rows, []int{1})
}
func main() {
var rows [][]int
addCopy(rows)
fmt.Println(len(rows)) // 0
addPtr(&rows)
fmt.Println(len(rows)) // 1
}
(*result)[level]. Indexing binds tighter than*, so the parentheses are required to dereference first and index second. The recursive calls passresulton as it is, since it already is a pointer.reverseworks in place. A row is a slice header pointing at an array that the slice inresultshares. Swapping elements through the copy thatreversereceived changes the same array, soresult[level]is reversed without returning anything.- Parallel assignment. Go evaluates every right-hand value before assigning any of them, so
row[i], row[j] = row[j], row[i]swaps without a temporary variable. Aforheader holds only one post statement, soi, j = i+1, j-1moves both indexes at once. - Field names. The value field is
Val, capitalized, as in the lesson'sTreeNode. - Empty tree.
resultstarts as an empty, non-nil[][]int{}, anddfsreturns immediately for anilroot, so the function returns an empty slice that prints as[].
Complexity
Time: O(n). The search visits each node once and does O(1) work per node, amortized: append occasionally copies, but its cost averages out. Reversing the odd levels touches each of their values once, which is at most n values in total.
Space: O(n). The rows hold all n values. On top of that, the recursion uses a stack as deep as the tree is tall, which is O(h): about log n for a balanced tree and up to n for a tree that is a single chain.
Edge cases and common mistakes
- Empty tree. A
nilroot returns an empty result. - Single node. The root alone gives
[[1]]. The reverse loop starts at level 1, which doesn't exist, so it doesn't run. - Missing children. In the tree with root 1, left child 2 (with a left child 4) and right child 3 (with a right child 5), the levels are
[1],[2, 3]and[4, 5], so the answer is[[1], [3, 2], [4, 5]]. Gaps don't matter: only the order of the nodes that exist does. - Visiting the right child first. That makes the even levels come out reversed and would flip the wrong rows. The reversal step assumes every row was collected left to right.
- Reversing the wrong levels. Starting the loop at 0 would reverse the root's row and every other row, giving the opposite zigzag. The root is read left to right, so the first level to flip is 1.
- Passing the slice by value. Without the pointer,
dfsappends to a copy, the caller'sresultstays empty, and the function returns[]for any tree. - Forgetting to assign back. Calling
append((*result)[level], root.Val)without assigning the result discards the value, and Go doesn't compile an expression statement like that:appendmust be used.
Testing
- Root 3 with children 9 and 20, where 20 has children 15 and 7, gives
[[3], [20, 9], [15, 7]]. - A single node with value 1 gives
[[1]]. - A
nilroot gives[]. - Root 1, left child 2 with left child 4, right child 3 with right child 5, gives
[[1], [3, 2], [4, 5]].
