Binary Tree Postorder Traversal — Problem & Solution
Binary Tree Postorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Binary Tree Postorder Traversal is an easy coding problem on depth-first search, trees and stack, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees, Stack
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the values of its nodes in postorder: for every node, first everything in its left subtree, then everything in its right subtree, and the node itself last.
Example 1
Input: root = [1,null,2,3]
Output: [3,2,1]
Explanation: 3 is the deepest node and comes first; the root 1 is always last.
Example 2
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,6,7,5,2,9,8,3,1]
Example 3
Input: root = [5]
Output: [5]
Constraints
The number of nodes in the tree is in the range [0, 100]-100 <= Node.val <= 100
Follow-up: The recursive walk is short — can you do it iteratively?
Hints for Binary Tree Postorder Traversal
Hint 1
In postorder a node is recorded only after both of its subtrees are finished — the root is always last.
Hint 2
A recursive helper that recurses left, recurses right and then appends the node follows the rule directly.
Hint 3
For an iterative version: a modified preorder (node, right, left) produces exactly the reverse of postorder.
How to solve Binary Tree Postorder Traversal
Postorder is left subtree, right subtree, then the node. A depth-first helper that appends a node after both of its recursive calls return writes the values in exactly that order.
Approach
- Define
walk(node): ifnodeis null, return. - Call
walk(node.left), thenwalk(node.right). - Append
node.valto the result. - Call
walk(root)and return the result.
Why it works
By induction on the height: walk lists a subtree in postorder because it first lists the left subtree in postorder, then the right one, then the subtree's root — which is the definition. An iterative alternative runs preorder with the children swapped (node, right, left) and reverses the list, since reversing that order gives left, right, node at every level.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion stack, O(n) for a chain-shaped tree
Pitfalls
- Appending before the recursive calls gives preorder.
- In the reversed-preorder trick, push the left child before the right one (the reverse of a normal preorder).
Reference solution
Python
from typing import List, Optional
def postorderTraversal(root: Optional[TreeNode]) -> List[int]:
out = []
def walk(node):
if node is None:
return
walk(node.left)
walk(node.right)
out.append(node.val)
walk(root)
return outJava
public static int[] postorderTraversal(TreeNode root) {
List<Integer> out = new ArrayList<>();
postWalk(root, out);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}
static void postWalk(TreeNode node, List<Integer> out) {
if (node == null) return;
postWalk(node.left, out);
postWalk(node.right, out);
out.add(node.val);
}C++
void postWalk(TreeNode* node, vector<int>& out) {
if (!node) return;
postWalk(node->left, out);
postWalk(node->right, out);
out.push_back(node->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> out;
postWalk(root, out);
return out;
}JavaScript
var postorderTraversal = function(root) {
var out = [];
postWalk(root, out);
return out;
};
var postWalk = function(node, out) {
if (node === null) return;
postWalk(node.left, out);
postWalk(node.right, out);
out.push(node.val);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals