N-ary Tree Postorder Traversal
Easy · Trees · Stack · Tree · Depth-First Search
Problem
Given the root of an n-ary tree (each node has a value and a list of children), return the postorder traversal of its values: visit each child's subtree from left to right, and only then the node itself.
The tree is written in level order, with each node's group of children followed by null as a separator. For example [1,null,3,2,4,null,5,6] is a root 1 with children 3, 2 and 4, where 3 has children 5 and 6.
The recursive version is short; try an iterative one too.
Examples
Input: root = [1,null,2,3,4,null,5,6,null,7] Output: [5,6,2,7,3,4,1]
Children are finished before their parent, so the root comes last: 5, 6, then 2; 7, then 3; 4; finally 1.
Input: root = [8] Output: [8]
A single node is its own traversal.
Input: root = [] Output: []
There are no nodes to visit.
Constraints
- The number of nodes is in the range [0, 10^4]
- 0 <= Node.val <= 10^4
- The height of the tree is at most 1000
Approaches
- Recursion that concatenates child lists — time O(n · h) for height h, space O(n · h) of copying, O(h) stack
Follow-up
Can you produce the postorder without reversing at the end? Keep (node, next child index) pairs on the stack: push the next unvisited child, and record a node only when all its children are done.
Related problems
Start free on Cariara · Coding problems · System design studio
