N-ary Tree Preorder Traversal solution and explanation
Google
9 more videos on this problem
LeetCode N-ary Tree Preorder Traversal Solution Explained - JavaNick White · 6:25 · 42K views
N-ary Tree Preorder Traversal | Live Coding with Explanation | Leetcode - 589Algorithms Made Easy · 10:04 · 12K views
LeetCode 589 | N-Ary Tree Pre-Order Traversal | Iterative + Recursive Solution (Java + Whiteboard)Xavier Elon · 9:46 · 2K views
N-ary Tree Preorder Traversal | Leetcode 589EasyLeetcode · 4:56 · 1K views
Обхід дерева N ary Tree Preorder Traversal: How to do it fast and easy! Leetcode - 589TechWorld-With-Yevgen · 7:01 · 547 views
589. N-ary Tree Preorder Traversal | Leetcode | PythonAbdullah Arshed · 5:29 · 516 views
589. N-ary Tree Preorder Traversal - LeetCode Java SolutionCode with Carter · 7:30 · 424 views
589. N-ary Tree Preorder Traversal | English | EasySimple Code - 단순코드 · 6:08 · 340 views
N-ary Tree Preorder Traversal - Google Interview Questions - LeetCode 589 Solution - C++nexTRIE · 3:26 · 289 views
Leetcode 589 - N-ary Tree Preorder Traversal (Java, Solution Explained)LC Bear · 4:48 · 230 views
The problem
Given the root of an n-ary tree, return the preorder 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: [1,3,5,6,2,4]
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: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
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 its preorder traversal. In preorder traversal, you visit the current node first, then recursively process each child from left to right.
Approach 1: Recursive DFS (Time: O(n), Space: O(h))
The most natural way to solve this problem is recursion using Depth-First Search. Start at the root, add the node's value to the result list, then recursively traverse each child in order. Because preorder requires visiting the node before its children, the operation sequence is: visit node → iterate children → recurse. Each node is processed exactly once, giving O(n) time complexity where n is the number of nodes. The recursion stack grows with the height of the tree, so the auxiliary space is O(h). This approach is concise and mirrors the definition of preorder traversal directly.
Approach 2: Iterative Traversal with Stack (Time: O(n), Space: O(n))
An iterative solution replaces recursion with an explicit stack. Push the root node onto the stack, then repeatedly pop the top node, record its value, and push its children onto the stack. The key detail is the order: push children in reverse order so the leftmost child is processed first when popped. This preserves preorder traversal order. Every node enters and leaves the stack once, so the time complexity remains O(n). The stack may contain up to O(n) nodes in the worst case (for example, a wide level in the tree). This method avoids recursion and works well in environments where recursion depth could be limited.
Recommended for interviews: The recursive DFS approach is usually expected first because it directly expresses preorder traversal and is easy to implement correctly. Interviewers often accept it as the primary solution. The iterative stack version demonstrates deeper understanding of traversal mechanics and recursion simulation, which can strengthen your answer if follow-up questions ask for an iterative implementation.
Approach 1: Recursive Approach
This approach leverages the simplicity of recursion to perform a preorder traversal on an n-ary tree. We start at the root node, then recursively process each child's subtree.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
class Solution:
def preorder(self, root: 'Node') -> List[int]:
def preorder_helper(node, result):
if not node:
return
result.append(node.val)
for child in node.children:
preorder_helper(child, result)
result = []
preorder_helper(root, result)
return resultimport java.util.ArrayList;
import java.util.List;
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> preorder(Node root) {
List<Integer> result = new ArrayList<>();
preorderHelper(root, result);
return result;
}
public void preorderHelper(Node node, List<Integer> result) {
if (node == null) return;
result.add(node.val);
for (Node child : node.children) {
preorderHelper(child, result);
}
}
}#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;
}
};
class Solution {
public:
void preorderHelper(Node* node, vector<int>& result) {
if (!node) return;
result.push_back(node->val);
for (Node* child : node->children) {
preorderHelper(child, result);
}
}
vector<int> preorder(Node* root) {
vector<int> result;
preorderHelper(root, result);
return result;
}
};class Node {
constructor(val, children = []) {
this.val = val;
this.children = children;
}
}
const preorder = function(root) {
const result = [];
const preorderHelper = (node) => {
if (!node) return;
result.push(node.val);
for (const child of node.children) {
preorderHelper(child);
}
};
preorderHelper(root);
return result;
};#include <stdio.h>
#include <stdlib.h>
// Definition for a Node.
struct Node {
int val;
int numChildren;
struct Node** children;
};
void preorderHelper(struct Node* node, int* returnArray, int* returnSize) {
if (node == NULL) return;
returnArray[(*returnSize)++] = node->val;
for (int i = 0; i < node->numChildren; i++) {
preorderHelper(node->children[i], returnArray, returnSize);
}
}
int* preorder(struct Node* root, int* returnSize) {
*returnSize = 0;
int* returnArray = malloc(10000 * sizeof(int)); // Assuming max size
preorderHelper(root, returnArray, returnSize);
return returnArray;
}using System.Collections.Generic;
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> Preorder(Node root) {
var result = new List<int>();
PreorderHelper(root, result);
return result;
}
private void PreorderHelper(Node node, IList<int> result) {
if (node == null) return;
result.Add(node.val);
foreach (var child in node.children) {
PreorderHelper(child, result);
}
}
}The Python solution uses a nested helper function named preorder_helper that appends node values to a list, result, as it recursively explores each subtree's preorder traversal starting from the root.
Time Complexity: O(n), n being the total number of nodes.
Space Complexity: O(n) due to the recursion stack's depth.
Approach 2: Iterative Approach with Stack
This approach uses an explicit stack to simulate the call stack of recursion. We manually manage traversals seen in recursion, starting from the root node, iteratively processing each node, then adding each child to a stack for future visits.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if not root:
return []
stack, result = [root], []
while stack:
node = stack.pop()
result.append(node.val)
stack.extend(reversed(node.children))
return resultimport java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
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> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
result.add(node.val);
List<Node> children = new ArrayList<>(node.children);
Collections.reverse(children);
for (Node child : children) {
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;
}
};
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> result;
if (!root) return result;
stack<Node*> stk;
stk.push(root);
while (!stk.empty()) {
Node* curr = stk.top();
stk.pop();
result.push_back(curr->val);
for (auto it = curr->children.rbegin(); it != curr->children.rend(); ++it) {
stk.push(*it);
}
}
return result;
}
};class Node {
constructor(val, children = []) {
this.val = val;
this.children = children;
}
}
const preorder = function(root) {
const result = [];
const stack = [];
if (root) stack.push(root);
while (stack.length) {
const node = stack.pop();
result.push(node.val);
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i]);
}
}
return result;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Definition for a Node.
struct Node {
int val;
int numChildren;
struct Node** children;
};
struct NodeStack {
struct Node* node;
struct NodeStack* next;
};
void push(struct NodeStack** stack, struct Node* node) {
struct NodeStack* new_node = (struct NodeStack*)malloc(sizeof(struct NodeStack));
new_node->node = node;
new_node->next = *stack;
*stack = new_node;
}
struct Node* pop(struct NodeStack** stack) {
if (*stack == NULL) return NULL;
struct NodeStack* temp = *stack;
struct Node* node = temp->node;
*stack = (*stack)->next;
free(temp);
return node;
}
bool isEmpty(struct NodeStack* stack) {
return stack == NULL;
}
int* preorder(struct Node* root, int* returnSize) {
*returnSize = 0;
if (!root) return NULL;
int* result = malloc(10000 * sizeof(int));
struct NodeStack* stack = NULL;
push(&stack, root);
while (!isEmpty(stack)) {
struct Node* node = pop(&stack);
result[(*returnSize)++] = node->val;
for (int i = node->numChildren - 1; i >= 0; i--) {
push(&stack, node->children[i]);
}
}
return result;
}using System.Collections.Generic;
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> Preorder(Node root) {
var result = new List<int>();
if (root == null)
return result;
Stack<Node> stack = new Stack<Node>();
stack.Push(root);
while (stack.Count > 0) {
Node currentNode = stack.Pop();
result.Add(currentNode.val);
for (int i = currentNode.children.Count - 1; i >= 0; i--) {
stack.Push(currentNode.children[i]);
}
}
return result;
}
}The Python code introduces a list-based manual stack managing the work of the traversal, maintaining the order of the node children such that earlier nodes are faced first due to reversing incorporation into the stack.
Time Complexity: O(n), the time through node visits.
Space Complexity: O(n), as characterized by stack in the worst-case storage condition.
Approach 3: Recursion
We can recursively traverse the entire tree. For each node, we first add the node's value to the answer, then recursively call the function for each of the node's children.
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 preorder(root: Node | null): number[] {
const ans: number[] = [];
const dfs = (root: Node | null) => {
if (!root) {
return;
}
ans.push(root.val);
for (const child of root.children) {
dfs(child);
}
};
dfs(root);
return ans;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func preorder(root *Node) (ans []int) {
var dfs func(*Node)
dfs = func(root *Node) {
if root == nil {
return
}
ans = append(ans, root.Val)
for _, child := range root.Children {
dfs(child)
}
}
dfs(root)
return
}Approach 4: Iteration (Stack Implementation)
We can also solve this problem iteratively.
We use a stack to help us get the pre-order traversal. We first push the root node into the stack. Since the pre-order traversal is root, left subtree, right subtree, 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 right to left. We continue this process until the stack is empty.
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 preorder(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);
for (let i = children.length - 1; i >= 0; i--) {
stk.push(children[i]);
}
}
return ans;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
func preorder(root *Node) (ans []int) {
if root == nil {
return
}
stk := []*Node{root}
for len(stk) > 0 {
node := stk[len(stk)-1]
ans = append(ans, node.Val)
stk = stk[:len(stk)-1]
children := node.Children
for i := len(children) - 1; i >= 0; i-- {
stk = append(stk, children[i])
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n), n being the total number of nodes. |
| Iterative Approach with Stack | Time Complexity: O(n), the time through node visits. |
| Recursion | – |
| Iteration (Stack Implementation) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(n) | O(h) | Best for clarity and typical interview solutions when recursion depth is manageable |
| Iterative Stack Traversal | O(n) | O(n) | Preferred when avoiding recursion or when practicing explicit stack-based DFS |
Frequently asked questions
Is N-ary Tree Preorder Traversal easy or hard?
N-ary Tree Preorder Traversal is classified as an easy problem. It mainly tests understanding of preorder traversal and DFS. Once you know the traversal order (node before children), the recursive implementation is short and direct.
N-ary Tree Preorder Traversal Python/Java solution
Python and Java solutions typically implement recursive DFS with a helper function that visits the node and then iterates through its children list. The iterative approach uses a stack (list in Python or Stack/Deque in Java) to simulate the recursion while maintaining preorder order.
How to solve N-ary Tree Preorder Traversal in O(n)?
Use depth-first search. Start at the root, append its value to the result, and recursively process each child in order. An iterative version uses a stack: pop a node, record its value, and push its children in reverse order so the leftmost child is processed first.
What is the best approach for N-ary Tree Preorder Traversal?
Recursive depth-first search is the most straightforward approach. Visit the current node, then recursively traverse each child from left to right. It runs in O(n) time because every node is visited once, and uses O(h) space for the recursion stack where h is the tree height.
Is N-ary Tree Preorder Traversal asked at Google/Amazon/Meta?
Tree traversal problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving binary trees, N-ary trees, and DFS traversal patterns are commonly used to test understanding of recursion, stacks, and tree data structures.
What data structure is used in N-ary Tree Preorder Traversal?
The traversal uses either the call stack through recursion or an explicit stack data structure for the iterative solution. The tree itself stores a list of children for each node, which you iterate through during the DFS process.
What is the time complexity of N-ary Tree Preorder Traversal?
The time complexity is O(n), where n is the number of nodes in the tree. Each node is visited exactly once during the traversal. Both recursive DFS and iterative stack implementations maintain the same time complexity.