Problem overview
The method postOrderTraversal receives the root of a binary tree and returns its values in post order: left subtree, right subtree, then the node itself. The root is a TreeNode | null.
For the tree built from [1,null,2,3], node 1 has only a right child, 2, and node 2 has a left child, 3. Post order gives [3,2,1]. The recursive solution is short; this lesson is the follow-up that avoids recursion by handling the stack yourself.
Approach: simulate the recursive calls
A recursive traversal relies on the call stack. Each call knows its node and remembers which of three actions it will do next: go left, go right, or record the node's value. When a call finishes, the call below it resumes where it stopped.
You can build exactly that with an array. Each stack entry is a pair: a node and the number of the step that call performs next. The steps are numbered 0 (go left), 1 (go right) and 2 (record the value). A step above 2 means the call has done everything.
The key trick: look at the top entry without removing it, move it on to its next step, and only then push the child's entry. When the child's entry is finished and popped, the parent is on top again, already at its next step. This reproduces the recursion's order, and because the value is recorded as the last action, the output is in post order.
This avoids the depth limit of the call stack. The explicit stack is an ordinary array on the heap, so a chain of tens of thousands of nodes is no problem.
Step by step
- Name the three steps as constants:
LEFT_CALLis 0,RIGHT_CALLis 1 andAPPEND_TO_TRAVERSALis 2. Names make the loop readable. - Create the output array,
traversal, typednumber[]. - Create the stack as an array of
[TreeNode | null, number]tuples. The node can benullbecause entries are pushed for missing children too. - Push the first entry,
[root, LEFT_CALL]. The traversal starts at the root, whose first action is to go left. - Loop while the stack is not empty.
- Read the top entry without removing it, destructuring it into
nodeandstep. The top is at indexstack.length - 1. - Discard finished entries. If the node is
null, or the step is already above 2, pop the entry and continue. The call below can now resume. - Advance this entry by replacing the top with
[node, step + 1], before pushing anything. - Act on the step that was read. At step 0, push the left child's entry. At step 1, push the right child's entry. Both start at
LEFT_CALL, because every call begins by going left. - At step 2, record the value by pushing
node.valontotraversal. Both children are already done at this point. - Return the traversal after the loop.
The solution in TypeScript
class Solution {
postOrderTraversal(root: TreeNode | null): number[] {
const LEFT_CALL = 0;
const RIGHT_CALL = 1;
const APPEND_TO_TRAVERSAL = 2;
const traversal: number[] = [];
const stack: [TreeNode | null, number][] = [];
stack.push([root, LEFT_CALL]);
while (stack.length > 0) {
let [node, step] = stack[stack.length - 1];
if (node == null || step > APPEND_TO_TRAVERSAL) {
stack.pop();
continue;
}
stack[stack.length - 1] = [node, step + 1];
if (step == LEFT_CALL) {
stack.push([node.left, LEFT_CALL]);
} else if (step == RIGHT_CALL) {
stack.push([node.right, LEFT_CALL]);
} else if (step == APPEND_TO_TRAVERSAL) {
traversal.push(node.val);
}
}
return traversal;
}
}
Here is how the stack behaves on a three-node tree, [1,2,3], with a root 1, left child 2 and right child 3. Each line shows the stack after an iteration, as (node, next step) pairs, with null for a missing child:
[1,1] [2,0]
[1,1] [2,1] [null,0]
[1,1] [2,2] [null,0]
[1,1] [2,3] value 2 recorded
[1,2] [3,0]
[1,2] [3,1] [null,0]
[1,2] [3,2] [null,0]
[1,2] [3,3] value 3 recorded
[1,3] value 1 recorded
The null entries and the finished entries are popped in the iterations between these lines, and the output is [2,3,1].
The TypeScript details worth a closer look:
- Tuple types.
[TreeNode | null, number]says each entry is a two-element array with a node first and a number second. Destructuringlet [node, step] = ...then givesnodeandstepthose types. At run time they are ordinary arrays. - Narrowing after the check. After the early
continueonnode == null, the compiler treatsnodeas aTreeNodebelow, sonode.leftandnode.valare accepted. node == null. The loose comparison tonullis also true forundefined. Here it only ever seesnull.- Replacing the top entry. Assigning to
stack[stack.length - 1]swaps in a new tuple. The destructuredstepkeeps the old value, which is why the branches below compare against the step that was just read. letin the loop. The destructuring creates fresh variables on every iteration, so no value leaks between iterations.
Complexity
Let n be the number of nodes and h the height.
Time: O(n). Each real node gets four loop iterations: three to run its steps and one to be popped. Each missing child is pushed once and popped once. The total is a constant times n.
Space: O(h) extra, plus the output. The stack holds one entry per node on the current path, plus the entry of a missing child at the top. That is O(h), and O(n) for a chain. Unlike recursion, the limit is memory, not the call stack depth.
Edge cases and common mistakes
- An empty tree. The stack starts with
[null, 0], which is popped at once. The method returns[]. - Advancing the step after pushing the child. Then the replace would overwrite the child's entry instead of the parent's. Always update the top before you push.
- Using the new step in the branches. The branches must compare with the step that was read, not
step + 1. Otherwise each action would run one step too early. - Recording the value at the wrong step. Recording it at step 0 gives pre order, and at step 1 gives in order. Step 2, after both children, gives post order.
- Forgetting
continue. Without it, the code below would run on anullnode and fail readingnode.left. - Assuming this is faster. It does the same work as the recursion. Its advantage is that it can't overflow the call stack.
Testing
[1,null,2,3]gives[3,2,1].[1,2,3]gives[2,3,1].[1,2,3,4,5,6,7]gives[4,5,2,6,7,3,1].- An empty tree gives
[].