Problem overview
The method postOrderTraversal receives the root of a binary tree and returns the values of its nodes in post order: for every node, the left subtree comes first, then the right subtree, and the node itself comes last. The root is a TreeNode | null, where null stands for an empty tree.
In the example, the tree is built from [1,null,2,3]. Node 1 has no left child and has node 2 as its right child, and node 2 has node 3 as its left child:
1
\
2
/
3
Post order visits 3 first, because it is the deepest node reached by going left and then right. Then comes 2, whose subtrees are done, and last comes 1. The result is [3,2,1].
Approach: recursion that mirrors the definition
The definition of post order is itself recursive: the traversal of a tree is the traversal of its left subtree, then the traversal of its right subtree, then the root's own value. An empty tree contributes nothing. Code can say exactly that.
A helper dfs(root, result) takes a node and an array. It walks the subtree below that node and appends each value to the array in post order. The public method creates the array, calls the helper once on the whole tree and returns the array.
The only thing that decides the order is where the push sits relative to the two recursive calls. Before them it gives pre order, between them in order, and after them post order. The lesson also mentions an iterative follow-up, which replaces the call stack with an explicit one. This lesson keeps to the recursive version, which is the shortest and the easiest to get right.
Step by step
- Write the public method first. Create an empty
number[]namedresult, call the helper onrootand returnresult. The helper is a method of the class, so it is reached throughthis. - Declare the helper. It takes the node, which may be
nullbecause the recursion reaches missing children, and the sharedresultarray. It returns nothing. - Stop on a missing node. If
rootisnull, return at once. This is the base case: an empty subtree adds nothing, and it ends every chain of calls. - Recurse into the left subtree with the same
result. Everything on the left is appended before anything else. - Recurse into the right subtree the same way. A missing child needs no separate check, because the base case handles it.
- Push the node's own value last. Both subtrees are finished at this point, which is what makes the order post order.
The solution in TypeScript
class Solution {
dfs(root: TreeNode | null, result: number[]): void {
if (!root) {
return;
}
this.dfs(root.left, result);
this.dfs(root.right, result);
result.push(root.val);
}
postOrderTraversal(root: TreeNode | null): number[] {
const result: number[] = [];
this.dfs(root, result);
return result;
}
}
The TypeScript details worth a closer look:
- Arrays are shared, not copied. The helper receives the same array object the caller created. Pushing inside any call changes that one array, so nothing has to be returned or merged.
constand the array.const resultprevents reassigning the variable. It does not preventpush.- Narrowing with
!root. After the early return, the compiler knows thatrootis aTreeNodefor the rest of the method. That is whyroot.leftandroot.valare accepted without extra checks. void. The return type says the helper produces no value. The barereturn;just ends the call early.- Calling through
this. Inside a class, a method calls its siblings withthis.dfs(...). Writing plaindfs(...)would look for a function outside the class and fail.
Complexity
Let n be the number of nodes and h the height of the tree.
Time: O(n). Each node is visited once and does a constant amount of work. Each missing child costs one extra call that returns immediately, and there are at most n + 1 of them.
Space: O(h) extra, plus the output. The recursion depth equals the height of the tree: O(log n) for a balanced tree and O(n) for a chain. The result array holds n values.
Edge cases and common mistakes
- An empty tree. With
rootequal tonull, the helper returns immediately and the method returns[]. - A single node. Both recursive calls hit the base case, and the result is just that node's value.
- Pushing too early. Pushing before the recursive calls gives pre order, so the example would return
[1,2,3]. Pushing between the two calls gives in order, which would return[1,3,2]for the example. - Swapping the two calls. Visiting the right subtree before the left one still ends with the node, but it gives a mirrored order.
- Very deep trees. Each level of the tree is one nested call. A tree shaped like a long chain, with tens of thousands of nodes, can exhaust the call stack and throw a
RangeError. With Node’s default stack, a left-leaning chain of 20,000 nodes is enough. The explicit-stack version avoids this. - Returning inside the helper. The helper's job is to fill
result. Only the public method returns it.
Testing
[1,null,2,3]gives[3,2,1].[1,2,3,4,5,6,7], a full tree, gives[4,5,2,6,7,3,1].- A single node
[1]gives[1]. - An empty tree gives
[].