Binary Tree Postorder Traversal
Easy · Trees · Stack · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree, return the postorder traversal of its values: the entire left subtree, then the entire right subtree, and the node itself last.
The recursive version is short. Try the iterative one too: it is the hardest of the three depth-first orders to do with a stack.
Examples
Input: root = [6,2,8,1,4] Output: [1,4,2,8,6]
Both children of 2 come before 2, and the root 6 comes last.
Input: root = [3,null,5,7] Output: [7,5,3]
The deepest node 7 comes first, then 5, then the root.
Input: root = [] Output: []
There is nothing to visit.
Constraints
- The tree has between 0 and 100 nodes
- -100 <= Node.val <= 100
Approaches
- Recursive walk — time O(n), space O(h) call stack
Follow-up
Postorder is the order in which a node can use its children's finished results, which is why it shows up in subtree sums, heights and deleting a tree. The use cases compute subtree sums in that order and take postorder to trees with any number of children, given as a parent list.
Related problems
Start free on Cariara · Coding problems · System design studio
