Problem overview
The function inorderTraversal receives the root of a binary tree, a *TreeNode, and returns the node values as an []int in inorder: the whole left subtree first, then the node itself, then the whole right subtree. The tree's nodes have a Val field and two pointer fields, Left and Right. A missing child is a nil pointer.
In the example the root 1 has no left child and a right child 2, and 2 has a left child 3. Inorder visits the (empty) left side of 1, then 1, then the right subtree of 1. Inside that subtree it visits 3, then 2. The result is [1, 3, 2].
Approach: let the definition drive the recursion
The definition of inorder is already recursive: to traverse a tree, traverse its left subtree, record the root, and traverse its right subtree. A subtree is itself a tree, so one function can call itself on root.Left and root.Right. The base case is the empty tree, a nil pointer, which contributes nothing.
The statement also mentions an iterative follow-up using an explicit stack. This lesson does the recursive version, which is shorter and maps directly onto the definition.
The one design question is where the results go. The helper inorderDfs doesn't return a slice. It fills one shared slice that inorderTraversal owns, and that sharing is why a pointer to the slice is involved.
Step by step
- Declare the helper.
inorderDfstakes the subtree'srootand aresultof type*[]int, and returns nothing. - Handle the empty subtree. If
rootisnil, return. This stops the recursion at the bottom of the tree. - Visit the left subtree by calling
inorderDfs(root.Left, result).resultis already a pointer, so it is passed along unchanged. - Record the node. Append
root.Valto*resultand store the returned slice back into*result. - Visit the right subtree with
root.Right. The order of these three actions is what makes the traversal inorder. - In
inorderTraversal, declareresultas an empty slice of ints. - Call the helper with
rootand&result, the address of the slice variable. - Return
result, which now holds every value in order.
The solution in Go
func inorderTraversal(root *TreeNode) []int {
result := []int{}
inorderDfs(root, &result)
return result
}
func inorderDfs(root *TreeNode, result *[]int) {
if root == nil {
return
}
inorderDfs(root.Left, result)
*result = append(*result, root.Val)
inorderDfs(root.Right, result)
}
The Go details worth a closer look:
- Why a pointer to a slice. A slice value is a small header: a pointer to an array, a length and a capacity. Passing a slice to a function copies that header. The function can change existing elements, and the caller sees those changes, but
appendreturns a new header with a larger length, and the copy is the only thing that gets it. A function that appended to a plain[]intparameter would leave the caller's slice with length 0. With*[]int, every call updates the one header thatinorderTraversalowns. *resultand&result. The&operator takes the address of a variable and gives a*[]int. The*operator goes the other way:*resultis the slice the pointer refers to, usable on the left of an assignment as well as on the right.appendneeds its result assigned.append(*result, root.Val)on its own does nothing useful, and Go rejects the statement because its result is unused. The assignment back to*resultis what stores the grown slice.- Nil pointers. Reading
root.Leftwhenrootisnilwould panic. Thenilcheck at the top of the function is what makes it safe to callinorderDfson a missing child. - Empty slice, not
nil.[]int{}is an empty slice with length 0. For an empty tree the function returns it, so the caller gets a slice that prints as[]. A slice declared withvar result []intwould work the same way here, sinceappendhandles a nil slice, but it would benilrather than empty for an empty tree. - Definition order.
inorderDfsis defined below the function that calls it. In Go, functions at package level can be used before their definition in the file.
Complexity
Time: O(n) for a tree with n nodes. Each node is visited once, plus one call per missing child, which is at most n + 1 extra calls. Each call does a constant amount of work. The append calls are amortised constant time, because the slice grows geometrically when it runs out of capacity.
Space: O(h) for the recursion, where h is the height of the tree, plus O(n) for the result itself. A balanced tree has h near log n. A tree where every node has only one child has h = n, and the call stack then holds n frames.
Edge cases and common mistakes
- An empty tree. With
root == nil, the helper returns at once and the function returns[]. - A single node. Both recursive calls hit
nil, and the result is just that node's value. - Passing the slice by value. With a parameter of type
[]intinstead of*[]int, the code compiles and runs, but the appends are lost and the function returns[]for every tree. - Wrong order of the three steps. Recording the value before the left call gives preorder, and recording it after the right call gives postorder. For the example tree these give
[1, 3, 2]and[3, 2, 1]. - Forgetting the
nilcheck. The first call on a leaf's child dereferences a nil pointer and the program panics. - Dereferencing the wrong way. Writing
result = append(result, root.Val)does not compile, becauseresultis a pointer andappendexpects a slice.
Testing
- The tree 1, right child 2, whose left child is 3, gives
[1 3 2]. - A tree of one node with value 7 gives
[7]. - An empty tree gives
[]. - A root 2 with children 1 and 3 gives
[1 2 3], which is sorted: inorder on a binary search tree always lists the values in ascending order.