Binary Tree Postorder Traversal
The key idea
Postorder means a node is recorded only AFTER both of its subtrees are done: left subtree, then right subtree, then the node itself. The last value emitted is always the root.
Problem
Given the root of a binary tree, return the postorder traversal of its nodes' values.
In postorder traversal you visit the left subtree first, then the right subtree, and finally the node itself. So a node's value is added to the result only after both of its children's subtrees have been fully processed. For an empty tree the answer is an empty list.
The classic recursive solution is straightforward. As a follow-up, can you also solve it iteratively using an explicit stack?
Constraints
- The number of the nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Examples
Input: root = [1,null,2,3]
Output: [3,2,1]
Input: root = []
Output: []
Input: root = [1]
Output: [1]
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY
- Count Good Nodes in Binary TreeMEDIUM