Skip to main content
Talentd

N-ary Tree Preorder Traversal - Solution & Explanation

EasyStackTreeDepth-First Search19 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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.

The C code defines a node structured to represent each tree node with value and children. Using a helper function, preorderHelper, it ensures the tree is traversed in preorder by accessing each node's value before recursively calling the helper on each child.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(n) for the recursion stack used in the helper function.

Try this approach in the editor →

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.

This C solution uses a stack structure to handle the iterative traversal. The stack manually manages nodes left to process, with each node added to the result upon visitation. It handles children in reverse order to maintain correct preorder evaluation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n). Space Complexity: O(n), as most nodes can be stored in the stack in the worst case.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptC

Python

Java

C++

Go

TypeScript

C

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach

Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(n) for the recursion stack used in the helper function.

Iterative Approach with Stack

Time Complexity: O(n). Space Complexity: O(n), as most nodes can be stored in the stack in the worst case.

Recursion—
Iteration (Stack Implementation)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DFSO(n)O(h)Best for clarity and typical interview solutions when recursion depth is manageable
Iterative Stack TraversalO(n)O(n)Preferred when avoiding recursion or when practicing explicit stack-based DFS

Video Solution

LeetCode N-ary Tree Preorder Traversal Solution Explained - Java • Nick White • 42,462 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice N-ary Tree Preorder Traversal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Preorder Traversal

Next

N-ary Tree Level Order Traversal