Binary Tree Postorder Traversal
Given the root of a binary tree, return the postorder traversal of its nodes' values. Postorder means Left, Right, Root: a node is recorded only after both its subtrees are done.
Constraints:
- The number of nodes is in the range
[0, 100]. -100 <= Node.val <= 100
Intuition
Every example below uses this tree:
1 12 / \3 2 34 / \ \5 4 5 6Postorder is bottom-up: children are always handled before their parent. For the tree above it gives 4, 5, 2, 6, 3, 1, and the root is always last.
This is the order you want whenever a node's answer depends on its children, for example computing height, deleting a tree, or evaluating an expression tree.
Approach: Recursion
- If the current node is
null, return. - Recurse on the left child.
- Recurse on the right child.
- Add the node's value to the answer.
The add line now comes after both recursive calls.
Code
class Solution {public:void dfs(TreeNode* node, vector<int>& ans) {if (node == nullptr) return;dfs(node->left, ans);dfs(node->right, ans);ans.push_back(node->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> ans;dfs(root, ans);return ans;}};
Complexity
Time: O(n)
Each node is visited exactly once.
Space: O(h)
Recursion stack depth equals the tree height: O(log n) when balanced, O(n) when skewed.
How to Explain It in an Interview
How to Explain it in an Interview
The 30-Second Spoken Pitch
"Postorder is left, right, root, so children are always finished before their parent. I recurse left, recurse right, and only then add the current value. The base case is a null node. This is the natural order when a node needs information from its children, like computing height or deleting a tree. Time is O of n since every node is visited once, and space is O of h for the recursion stack."
Next TopicBinary Tree Level Order Traversal