Easy difficulty · Algorithm · Topics: tree, traversal, dfs, recursion
Postorder traversal visits the left subtree, then the right subtree, and the node itself last. Every node is therefore processed after all its descendants, which is exactly what you need to delete a tree, compute sizes/heights bottom-up, or evaluate an expression tree. The tree is passed as a level-order array and built into nodes inside the function.
Think of packing boxes that contain smaller boxes: you must pack (and close) the inner boxes before you can close the outer one. Postorder encodes that "children first, parent last" rule, and the root is always the final value.
Why it works: visit(node) recurses into both children before it records node.val, so by the time a node is recorded, its whole subtree is already in result.
node is null, return.node.left.node.right.node.val.visit(root).Two-stack iterative variant (not in the code): run a modified preorder (node, right, left) using , but instead of recording a node, push it onto . Pop , push the node onto , then push its left child and its right child onto . At the end, popping yields the nodes in left, right, node order, because reversing "node, right, left" gives "left, right, node". A one-stack variant tracks the last visited node to know when a node's right subtree is finished.
stack1stack2stack1stack2stack1stack2Test case 0, tree [1, 2, 3, 4, 5, null, 6]:
1
/ \
2 3
/ \ \
4 5 6
| Event | result |
|---|---|
visit(1) -> visit(2) -> visit(4): both children null, record 4 | [4] |
back in 2, visit(5): record 5 | [4, 5] |
| both children of 2 done, record 2 | [4, 5, 2] |
back in 1, visit(3): left is null, visit(6) records 6 | [4, 5, 2, 6] |
| record 3 | [4, 5, 2, 6, 3] |
| record 1 (the root, last) | [4, 5, 2, 6, 3, 1] |
| Measure | Cost | Why |
|---|---|---|
| Time | O(n) | Every node is visited once |
| Space | O(h) | Recursion depth equals the tree height: O(log n) balanced, O(n) for a chain (the two-stack variant uses O(n)) |
result never starts with the root; the root appears last.null.Input: root = [1, 2, 3, 4, 5, null, 6]
Output: [4, 5, 2, 6, 3, 1]
function postorderTraversal(values) {
const root = buildTree(values);
const result = [];
// Postorder: left subtree, right subtree, and the node itself LAST.
function visit(node) {
if (node === null) return;
visit(node.left);
visit(node.right);
result.push(node.val);
}
visit(root);
return result;
}
// Build a binary tree from a level-order array (null = missing child).
function buildTree(values) {
const nodes = values.map((v) => (v === null ? null : new TreeNode(v)));
let next = 1;
for (const node of nodes) {
if (node === null) continue;
if (next < nodes.length) node.left = nodes[next++];
if (next < nodes.length) node.right = nodes[next++];
}
return nodes.length > 0 ? nodes[0] : null;
}