DSA problem
Binary Tree Postorder Traversal
Given the root of a binary tree, return the postorder traversal of its nodes' values. Postorder visits each node in the order left subtree → right subtree → root, so the root is always the last value emitted, preceded by the full left subtree and then the full right subtree, each recursively in postorder.
Postorder is the natural traversal whenever you want to process a node after both of its children have already been processed. It is the cornerstone of bottom-up tree algorithms: computing subtree heights, deleting a tree, evaluating postfix expressions, or any problem where the parent's answer depends on aggregating results from the children. Almost every "return information up the tree" pattern is structurally a postorder traversal.
The recursive solution is a textbook three-liner: recurse left, recurse right, then visit the current node. It is clean and obvious, but it consumes O(h) stack frames where h is the height of the tree, which degrades to O(n) for a skewed tree.
The iterative solution is the interesting one. A clean trick is to perform a modified preorder in the order root → right → left (a mirror of true preorder), then reverse the result — what you collected as "root, right, left" reverses into "left, right, root", exactly postorder. Below we show that approach because it uses a single explicit stack and avoids the "last visited" bookkeeping that a literal iterative postorder requires. Both forms run in O(n) time; the reverse-mirror form is the cleanest iterative version you can write under interview pressure.
Examples
root = [1,null,2,3][3,2,1]root = [][]root = [1,2,3,4,5,null,6][4,5,2,6,3,1]Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
- The tree is a valid binary tree (each node has at most two children).
- Follow-up: an iterative O(n)-time, O(h)-space solution is expected.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.