N-ary Tree Postorder Traversal - Solution & Explanation
Problem Statement
Given the root of an n-ary tree, return the postorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
Example 1:
Input: root = [1,null,3,2,4,null,5,6] Output: [5,6,3,2,4,1]
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. 0 <= Node.val <= 104- The height of the n-ary tree is less than or equal to
1000.
Follow up: Recursive solution is trivial, could you do it iteratively?
Approach Overview
Problem Overview: Given the root of an N-ary tree, return the postorder traversal of its nodes' values. Postorder means visiting all children of a node first, then the node itself.
This problem checks your understanding of tree traversal patterns. Unlike binary trees, each node can have multiple children, so your traversal logic must iterate through an arbitrary list of children before processing the parent node.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
The most natural solution uses recursion. For each node, recursively traverse all its children from left to right, then append the node's value to the result list. This directly matches the definition of postorder traversal. The recursion stack handles traversal order automatically, making the implementation short and easy to reason about.
The key operation is iterating through node.children and calling DFS on each child before adding the current node's value. Every node is visited exactly once, giving O(n) time complexity. Space complexity is O(h), where h is the tree height, due to the recursive call stack. This approach is commonly expected in interviews when discussing depth-first search.
Approach 2: Iterative Traversal Using Stack (Time: O(n), Space: O(n))
If recursion is not preferred, you can simulate the traversal with an explicit stack. Start by pushing the root node. While the stack is not empty, pop a node, add its value to the result, and push its children onto the stack. Since this produces a modified preorder traversal (root before children), reverse the result list at the end to obtain the correct postorder order.
The trick is that reversing a root-first traversal effectively produces children-before-root ordering. Each node is pushed and popped once, so the time complexity remains O(n). The stack may store many nodes simultaneously, especially in wide trees, giving a worst-case space complexity of O(n).
Recommended for interviews: Start with the recursive DFS solution. It clearly expresses postorder logic and demonstrates strong understanding of tree traversal. Follow up with the iterative stack approach if the interviewer asks about avoiding recursion or implementing traversal manually.
Approach 1: Recursive Approach
This approach utilizes recursion to traverse the N-ary tree in a postorder fashion. For each node, we recursively visit all its children first before processing the node itself.
This implementation defines a helper function postorderHelper that performs the recursive traversal. The function visits each child of the current node before appending the node's value to the result array. The main function postorder initializes the result array and calls the helper function.
Complexity
Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) for the recursion stack in the worst case (maximum tree height).
Approach 2: Iterative Approach with Stack
This approach uses an iterative method to perform postorder traversal with the help of a stack to simulate recursion. Nodes are pushed onto the stack in such a way that their children are processed before the node itself.
This C solution uses a stack to hold nodes and their visitation state. Nodes are pushed onto the stack to revisit them later for value recording, ensuring that each node's children are processed before the node itself, mimicking postorder traversal.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Recursion
We can recursively traverse the entire tree. For each node, we first recursively call the function for each of the node's children, then add the node's value to the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Iteration (Stack Implementation)
We can also solve this problem iteratively.
We use a stack to help us get the post-order traversal. We first push the root node into the stack. Since the post-order traversal is left subtree, right subtree, root, and the characteristic of the stack is first in last out, we first add the node's value to the answer, then push each of the node's children into the stack in the order from left to right. This way, we can get the traversal result of root, right subtree, left subtree. Finally, we reverse the answer to get the post-order traversal result.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n), where n is the number of nodes, as each node is visited once. |
| Iterative Approach with Stack | Time Complexity: O(n) |
| Recursion | — |
| Iteration (Stack Implementation) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(n) | O(h) | Best for clarity and interview explanations when recursion depth is manageable |
| Iterative Stack Traversal | O(n) | O(n) | When recursion is restricted or you want explicit control over traversal |
Video Solution
LeetCode N-ary Tree Postorder Traversal Solution Explained - Java • Nick White • 52,543 views views
Watch 9 more video solutions →Frequently Asked Questions
Is N-ary Tree Postorder Traversal easy or hard?
N-ary Tree Postorder Traversal Python/Java solution
How to solve N-ary Tree Postorder Traversal in O(n)?
What is the best approach for N-ary Tree Postorder Traversal?
Is N-ary Tree Postorder Traversal asked at Google/Amazon/Meta?
What data structure is used in N-ary Tree Postorder Traversal?
What is the time complexity of N-ary Tree Postorder Traversal?
Ready to solve this problem?
Practice N-ary Tree Postorder Traversal with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor