N-ary Tree Postorder Traversal solution and explanation
Google
9 more videos on this problem
LeetCode N-ary Tree Postorder Traversal Solution Explained - JavaNick White · 7:20 · 52K views
N-ary Tree Postorder Traversal - Leetcode 590 - PythonNeetCodeIO · 9:50 · 11K views
PostOrder Traversal | LeetCode 590 🏆 | FAANG 🔥 | Generic/N-ary Trees | Detailed ExplanationThe FinTech Club · 6:06 · 2K views
LeetCode 590 | N-ary Tree Postorder TraversalXavier Elon · 10:50 · 1K views
N-ARY TREE POSTORDER TRAVERSAL | LEETCODE 590 | PYTHON ITERATIVE SOLUTIONCracking FAANG · 8:07 · 439 views
Leetcode 590 - N-ary Tree Postorder Traversal (Java, Solution Explained)LC Bear · 5:12 · 425 views
Daily Leetcode #1609: Aug 26, 2024 - 590. N-ary Tree Postorder TraversalProgramming Live with Larry · 5:44 · 244 views
LeetCode 590 | N-ary Tree Postorder Traversal | Python | DFSSoupzzz · 4:06 · 57 views
590. N-ary Tree Postorder Traversal | Leetcode | #leetcode #leetcodejavaCode Monger · 9:55 · 49 views
590. N-ary Tree Postorder Traversal | Easy Level Interview Question Full Explanation in PythonEduEverybody · 7:34 · 46 views
The problem
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.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
class Solution:
def postorder(self, root: 'Node') -> List[int]:
def recurse(node):
if not node:
return
for child in node.children:
recurse(child)
output.append(node.val)
output = []
recurse(root)
return outputimport java.util.*;
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> result = new ArrayList<>();
postorderHelper(root, result);
return result;
}
private void postorderHelper(Node node, List<Integer> result) {
if (node == null) return;
for (Node child : node.children) {
postorderHelper(child, result);
}
result.add(node.val);
}
}#include <vector>
using namespace std;
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
void postorderHelper(Node* root, vector<int>& result) {
if (root == nullptr) return;
for (auto child : root->children) {
postorderHelper(child, result);
}
result.push_back(root->val);
}
vector<int> postorder(Node* root) {
vector<int> result;
postorderHelper(root, result);
return result;
}function Node(val, children) {
this.val = val;
this.children = children || [];
}
var postorder = function(root) {
const result = [];
function traverse(node) {
if (node === null) return;
for (let child of node.children) {
traverse(child);
}
result.push(node.val);
}
traverse(root);
return result;
};#include <stdio.h>
#include <stdlib.h>
struct Node {
int val;
int numChildren;
struct Node** children;
};
void postorderHelper(struct Node* root, int* returnSize, int* result) {
if (root == NULL) return;
for (int i = 0; i < root->numChildren; i++) {
postorderHelper(root->children[i], returnSize, result);
}
result[(*returnSize)++] = root->val;
}
int* postorder(struct Node* root, int* returnSize) {
int* result = (int*)malloc(10000 * sizeof(int));
*returnSize = 0;
postorderHelper(root, returnSize, result);
return result;
}public class Node {
public int val;
public IList<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, IList<Node> _children) {
val = _val;
children = _children;
}
}
public class Solution {
public IList<int> Postorder(Node root) {
List<int> result = new List<int>();
PostorderHelper(root, result);
return result;
}
private void PostorderHelper(Node node, List<int> result) {
if (node == null) return;
foreach (var child in node.children) {
PostorderHelper(child, result);
}
result.Add(node.val);
}
}Python's solution follows the recursive strategy with an inner function recurse for traversal. This function is called with each child node and appends the current node value to the result list. The main function initiates the result list and starts the traversal with the root node.
Time Complexity: O(n) since each node is visited once.
Space Complexity: O(n) because of the recursion stack and output list.
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.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
class Solution:
def postorder(self, root: 'Node') -> List[int]:
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
stack.extend(node.children)
return result[::-1]import java.util.*;
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
class Solution {
public List<Integer> postorder(Node root) {
LinkedList<Integer> result = new LinkedList<>();
if (root == null) return result;
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
result.addFirst(node.val);
for (Node child : node.children) {
if (child != null) stack.push(child);
}
}
return result;
}
}#include <vector>
#include <stack>
using namespace std;
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
vector<int> postorder(Node* root) {
vector<int> result;
if (root == nullptr) return result;
stack<Node*> stk;
stk.push(root);
while (!stk.empty()) {
Node* node = stk.top();
stk.pop();
result.insert(result.begin(), node->val);
for (Node* child : node->children) {
if (child) stk.push(child);
}
}
return result;
}function Node(val, children) {
this.val = val;
this.children = children || [];
}
var postorder = function(root) {
if (!root) return [];
const stack = [root];
const result = [];
while (stack.length) {
const node = stack.pop();
result.unshift(node.val);
for (const child of node.children) {
if (child !== null) stack.push(child);
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct Node {
int val;
int numChildren;
struct Node** children;
};
struct StackElement {
struct Node* node;
bool visited;
};
int* postorder(struct Node* root, int* returnSize) {
struct Node* stack[10000];
int top = -1;
struct StackElement stackElem[10000];
int elemTop = -1;
int* result = (int*)malloc(10000 * sizeof(int));
*returnSize = 0;
if (root != NULL) {
stackElem[++elemTop].node = root;
stackElem[elemTop].visited = false;
}
while (elemTop > -1) {
struct StackElement topElem = stackElem[elemTop--];
if (topElem.visited) {
result[(*returnSize)++] = topElem.node->val;
} else {
stackElem[++elemTop].node = topElem.node;
stackElem[elemTop].visited = true;
for (int i = topElem.node->numChildren - 1; i >= 0; --i) {
stackElem[++elemTop].node = topElem.node->children[i];
stackElem[elemTop].visited = false;
}
}
}
return result;
}public class Node {
public int val;
public IList<Node> children;
public Node() {}
public Node(int _val) { val = _val; }
public Node(int _val, IList<Node> _children) { val = _val; children = _children; }
}
public class Solution {
public IList<int> Postorder(Node root) {
List<int> result = new List<int>();
if (root == null) return result;
Stack<Node> stack = new Stack<Node>();
stack.Push(root);
while (stack.Count > 0) {
Node node = stack.Pop();
result.Insert(0, node.val);
foreach (var child in node.children) {
if (child != null) stack.Push(child);
}
}
return result;
}
}Python's iterative solution relies on a stack. Nodes are processed using a stack then prepended to the result list for postorder. A final reversal of result after processing gives the correct postorder traversal.
Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) associated with stack storage and the result reversal.
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.
/**
* Definition for node.
* class Node {
* val: number
* children: Node[]
* constructor(val?: number) {
* this.val = (val===undefined ? 0 : val)
* this.children = []
* }
* }
*/
function postorder(root: Node | null): number[] {
const ans: number[] = [];
const dfs = (root: Node | null) => {
if (!root) {
return;
}
for (const child of root.children) {
dfs(child);
}
ans.push(root.val);
};
dfs(root);
return ans;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func postorder(root *Node) (ans []int) {
var dfs func(*Node)
dfs = func(root *Node) {
if root == nil {
return
}
for _, child := range root.Children {
dfs(child)
}
ans = append(ans, root.Val)
}
dfs(root)
return
}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.
/**
* Definition for node.
* class Node {
* val: number
* children: Node[]
* constructor(val?: number) {
* this.val = (val===undefined ? 0 : val)
* this.children = []
* }
* }
*/
function postorder(root: Node | null): number[] {
const ans: number[] = [];
if (!root) {
return ans;
}
const stk: Node[] = [root];
while (stk.length) {
const { val, children } = stk.pop()!;
ans.push(val);
stk.push(...children);
}
return ans.reverse();
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func postorder(root *Node) []int {
var ans []int
if root == nil {
return ans
}
stk := []*Node{root}
for len(stk) > 0 {
root = stk[len(stk)-1]
stk = stk[:len(stk)-1]
ans = append([]int{root.Val}, ans...)
for _, child := range root.Children {
stk = append(stk, child)
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n) since each node is visited once. |
| Iterative Approach with Stack | Time Complexity: O(n) where n is the number of nodes. |
| Recursion | – |
| Iteration (Stack Implementation) | – |
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 |
Frequently asked questions
Is N-ary Tree Postorder Traversal easy or hard?
N-ary Tree Postorder Traversal is considered an easy problem. The main requirement is understanding DFS traversal order and adapting it from binary trees to nodes that may contain multiple children.
N-ary Tree Postorder Traversal Python/Java solution
In Python or Java, implement a DFS function that iterates through node.children and recursively processes each child before appending the node value to a result list. Both languages produce a clean O(n) implementation with minimal code.
How to solve N-ary Tree Postorder Traversal in O(n)?
Use depth-first search to visit every node once. Recursively traverse each child of the current node and append the node value after all children are processed. An iterative version using a stack and reversing the result also achieves O(n) time.
What is the best approach for N-ary Tree Postorder Traversal?
The recursive depth-first search approach is the most common and easiest to implement. Traverse all children of a node first and then add the node value to the result. This directly follows the definition of postorder traversal and runs in O(n) time with O(h) recursion stack space.
Is N-ary Tree Postorder Traversal asked at Google/Amazon/Meta?
Tree traversal problems are common in interviews at companies like Google, Amazon, and Meta. Variations of N-ary tree traversal test understanding of DFS, recursion, and stack-based traversal techniques.
What data structure is used in N-ary Tree Postorder Traversal?
The core structure is an N-ary tree where each node contains a list of children. Implementations typically use recursion (implicit stack) or an explicit stack data structure to perform depth-first traversal.
What is the time complexity of N-ary Tree Postorder Traversal?
The time complexity is O(n) because every node in the tree is visited exactly once. Whether using recursion or an iterative stack, each node is processed a single time during traversal.