Problem overview
The function postOrderTraversal receives the root of a binary tree, a *TreeNode with fields Val, Left and Right, and returns the values in post order: left subtree, right subtree, then the node. This lesson answers the statement's follow-up and does it iteratively, without recursive calls.
For the tree [1,null,2,3], node 1 has only a right child 2, and 2 has a left child 3. The result is [3, 2, 1].
Approach: keep the recursion's bookkeeping yourself
A recursive traversal is a function that does three things in order: call itself on the left child, call itself on the right child, then record the value. The language keeps a call stack that remembers, for every active call, which of the three actions it will do next.
The iterative version builds that memory by hand. Each stack entry holds a node and a step number:
- step 0: go left,
- step 1: go right,
- step 2: record the node's value,
- anything above 2: the call is finished.
The loop looks at the top entry and moves its step forward before doing the action. When the action is "go left", it pushes the left child as a new entry starting at step 0. That entry sits above its parent, so the child is finished and popped before the parent continues with its next step. This is exactly what a returning function call does.
Trace on the tree [1,2,3], with 2 as the left child and 3 as the right one. The stack starts as (1, step 0). Step 0 of node 1 pushes node 2. Node 2 goes left to a nil entry, which is popped at once, then right to another nil entry, then reaches step 2 and records 2. Node 1 resumes at step 1, handles node 3 the same way and records 3, and finally reaches step 2 and records 1. The result is [2, 3, 1].
A common alternative is a modified pre-order traversal whose output is reversed at the end. This lesson keeps the general technique, which also works for in-order and pre-order by changing when the value is recorded.
Step by step
- Name the steps with three constants:
leftCallis 0,rightCallis 1 andappendToTraversalis 2. - Create
traversalas an empty[]int. - Define a local struct named
statewith anodefield of type*TreeNodeand astepfield of typeint. Go has no tuples, so a small struct holds the pair. - Create
stackas an empty[]state. - Push the first entry,
state{root, leftCall}. The traversal begins at the root, and every call begins by going left. - Loop with
for len(stack) > 0. Go has nowhile; aforwith only a condition does the job. - Read the top entry into
nodeandstepwithout removing it. - Finish calls. If
nodeisnilorstepis greater thanappendToTraversal, pop the entry andcontinue. Anilentry is an empty subtree, and a step above 2 means all three actions are done. - Advance the top entry by overwriting it with
state{node, step + 1}. - Step 0: push
state{node.Left, leftCall}, the call for the left child. - Step 1: push
state{node.Right, leftCall}. The right child's call also starts at step 0. - Step 2: append
node.Valtotraversal. Both subtrees are finished by now, which is what makes this post order. - Return
traversalafter the loop.
The solution in Go
func postOrderTraversal(root *TreeNode) []int {
const leftCall = 0
const rightCall = 1
const appendToTraversal = 2
traversal := []int{}
type state struct {
node *TreeNode
step int
}
stack := []state{}
stack = append(stack, state{root, leftCall})
for len(stack) > 0 {
node := stack[len(stack)-1].node
step := stack[len(stack)-1].step
if node == nil || step > appendToTraversal {
stack = stack[:len(stack)-1]
continue
}
stack[len(stack)-1] = state{node, step + 1}
if step == leftCall {
stack = append(stack, state{node.Left, leftCall})
} else if step == rightCall {
stack = append(stack, state{node.Right, leftCall})
} else if step == appendToTraversal {
traversal = append(traversal, node.Val)
}
}
return traversal
}
The Go details worth a closer look:
- Local declarations. Constants and types can be declared inside a function, and they are visible only there.
statedoesn't clash with anything else in the package. - Untyped constants.
const leftCall = 0has no fixed type until it is used, so it fits theintfield instate{root, leftCall}and compares with theintvariablestep. - Unkeyed struct literals.
state{root, leftCall}lists the values in field order, so it is shorter thanstate{node: root, step: leftCall}. It breaks if the fields are later reordered, but for a private two-field type it is fine. - Entries are values. The stack holds
statestructs, not pointers. The linestack[len(stack)-1] = state{node, step + 1}replaces the whole top entry, and the local variablesnodeandstepstill hold the old values for the branches below. - Why
nilentries are pushed. Missing children go on the stack too, which keeps the loop uniform: the singlenode == niltest removes them. - Pop and push.
stack[:len(stack)-1]pops without copying, andappendpushes. The result of each is assigned back tostack.
Complexity
Time: O(n). Each real node is on the stack for four loop iterations (three steps plus the final pop), and each missing child costs one push and one pop.
Space: O(h) for the stack, where h is the height of the tree, plus O(n) for the output. The stack holds one entry per node on the current root-to-node path, plus at most one short-lived nil entry.
Edge cases and common mistakes
- Empty tree. The first entry holds a
nilnode, which is popped immediately. The function returns[]. - Advancing after the push. If the entry were updated after pushing the child, the update would overwrite the child's entry instead of the parent's, since the child is now on top. The advance must happen first.
- Starting a child at the wrong step. Every new call starts at
leftCall. Starting the right child atrightCallwould skip its left subtree. - Reading the fields after the pop. The code reads
nodeandstepinto variables before changing the stack, so later lines don't touch the slice again. - Dereferencing
nil.node.Leftwould panic on a missing node. Theniltest comes before any field access.
Testing
[1,null,2,3]gives[3, 2, 1].[1]gives[1].- An empty tree gives
[]. [1,2,3,4,5,6,7]gives[4, 5, 2, 6, 7, 3, 1].