On this page

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 1
2 / \
3 2 3
4 / \ \
5 4 5 6

Postorder 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

  1. If the current node is null, return.
  2. Recurse on the left child.
  3. Recurse on the right child.
  4. 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