Problem overview
The function postOrderTraversal receives the root of a binary tree, a *TreeNode, and returns the node values in post order: the left subtree first, then the right subtree, and the node itself last. Each node has an int field Val and two child pointers, Left and Right, which are nil when the child is missing.
In the example, the tree [1,null,2,3] has root 1 with no left child and a right child 2, whose left child is 3. Post order reaches 3 first, then 2, then 1, so the result is [3, 2, 1]. The statement's follow-up asks for an iterative version; this lesson is the recursive one, and a second lesson on the same problem does it iteratively.
Approach: visit the children, then the node
A tree is a node with two smaller trees below it, so recursion matches its shape. To traverse a tree in post order:
- Traverse the left subtree.
- Traverse the right subtree.
- Record the node's own value.
The only difference between the three classic orders is where step 3 sits. Recording the value first gives pre order, recording it between the two traversals gives in order, and recording it last gives post order. A missing child is an empty tree, and an empty tree contributes nothing, which gives the base case.
Each call needs somewhere to put its value. Rather than building and merging a new slice in every call, the lesson shares one result slice among all the recursive calls. In Go that raises one question: how can a helper grow a slice that belongs to its caller?
Step by step
- In
postOrderTraversal, createresultas an empty[]int, call the helperpostOrderDfs(root, &result), and returnresult. The&passes the address of the slice variable. - Declare the helper outside it, with the parameters
root *TreeNodeandresult *[]intand no return value. - Stop on
nil. Ifrootisnil, return at once. This check also handles missing children, so the calls below need no checks of their own. - Recurse left with
root.Left, passing the sameresultpointer along. - Recurse right with
root.Right. - Record the value last with
*result = append(*result, root.Val). Because this line comes after both recursive calls, the order is post order.
The solution in Go
func postOrderTraversal(root *TreeNode) []int {
result := []int{}
postOrderDfs(root, &result)
return result
}
func postOrderDfs(root *TreeNode, result *[]int) {
if root == nil {
return
}
postOrderDfs(root.Left, result)
postOrderDfs(root.Right, result)
*result = append(*result, root.Val)
}
The Go details worth a closer look:
- Why a pointer to the slice. A slice value is a small header holding a pointer to an array, a length and a capacity. Passing it to a function copies that header.
appendreturns a new header, and the helper would assign it to its own copy, so the caller would never see the new element. Withresult *[]intthe helper changes the caller's header through the pointer. For example, a functionfunc byValue(r []int) { r = append(r, 1) }called on an empty slice leaves it with length 0, whilefunc byPointer(r *[]int) { *r = append(*r, 1) }leaves it with length 1. *resultand&result.&resulttakes an address, and*resultfollows one. In the helper,resultalone is the pointer and*resultis the slice it points to. The recursive calls pass the pointer on unchanged.- Nil pointers as empty trees. A
*TreeNodecan benil, androot == nilis the correct test. Readingroot.Valon anilpointer panics, so the check must come before any field access. []int{}versusnil. The result starts as an empty, non-nil slice, so an empty tree returns[]rather thannil.- Declaration order. The helper is declared after the function that calls it, which Go allows at package level.
Complexity
Time: O(n). Every node is visited once, and each visit does a constant amount of work, plus the missing-child calls that return immediately. append is amortized constant time.
Space: O(h) for the call stack, plus O(n) for the output, where h is the height of the tree. A balanced tree has h around log n, and a tree where every node has one child has h = n.
Edge cases and common mistakes
- Empty tree. A
nilroot returns[]immediately. - Single node. The tree
[1]gives[1]: both children are empty, and the node is recorded. - Passing the slice by value. The code compiles and runs but returns an empty slice, a silent bug.
- Recording the value in the wrong place. Moving the
appendline to the top gives pre order, and for[1,null,2,3]that returns[1, 2, 3]. - Skipping the
nilcheck. Without it, the first leaf calls the helper on a missing child, androot.Lefton anilpointer panics. - Forgetting the dereference. Writing
result = append(result, root.Val)in the helper does not compile, sinceresultis a pointer, not a slice.
Testing
[1,null,2,3]gives[3, 2, 1].[1]gives[1].- An empty tree gives
[]. [1,2,3,4,5,6,7], a full tree of three levels, gives[4, 5, 2, 6, 7, 3, 1].