Binary Tree Postorder Traversal
EasyPrompt
Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Explanation:
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]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of the nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Approaches
4 approaches with complexity analysis and trade-offs.
The most intuitive approach to postorder traversal is using recursion. This method directly follows the definition of postorder traversal: traverse the left subtree, then the right subtree, and finally visit the root node. A helper function is typically used to manage the recursive calls.
Algorithm
- Define a helper function, say
traverse(node, resultList). - The base case for the recursion is if the
nodeisnull, in which case we simply return. - If the node is not null, recursively call the
traversefunction for the left child:traverse(node.left, resultList). - After the left subtree has been fully explored, recursively call the
traversefunction for the right child:traverse(node.right, resultList). - Finally, after both left and right subtrees have been traversed, add the value of the current node to the
resultList:resultList.add(node.val). - The main function initializes an empty list and calls the helper function with the root of the tree.
Walkthrough
This approach leverages the call stack to keep track of the nodes. When a function is called for a node, it first makes a recursive call for its left child. This process continues until a null node is reached. Then, the execution unwinds, and a recursive call is made for the right child. Only after both the left and right recursive calls for a node have returned, is the node's value added to the result list. This naturally ensures the 'Left -> Right -> Root' order.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); traverse(root, result); return result; } private void traverse(TreeNode node, List<Integer> result) { if (node == null) { return; } // 1. Traverse left subtree traverse(node.left, result); // 2. Traverse right subtree traverse(node.right, result); // 3. Visit the root result.add(node.val); }}Complexity
Time
O(N)
Space
O(H)
Trade-offs
Pros
The code is simple, clean, and easy to understand as it directly maps to the definition of postorder traversal.
Cons
For a very deep or skewed tree, the recursion depth can become very large, potentially leading to a
StackOverflowError.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Integer > postorderTraversal ( TreeNode root ) { LinkedList < Integer > ans = new LinkedList <>(); while ( root != null ) { if ( root . right == null ) { ans . addFirst ( root . val ); root = root . left ; } else { TreeNode next = root . right ; while ( next . left != null && next . left != root ) { next = next . left ; } if ( next . left == null ) { ans . addFirst ( root . val ); next . left = root ; root = root . right ; } else { next . left = null ; root = root . left ; } } } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.