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:
[0, 104].0 <= Node.val <= 1041000.
Follow up: Recursive solution is trivial, could you do it iteratively?
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.
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.
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.
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.
Time Complexity: O(n). Space Complexity: O(n), as most nodes can be stored in the stack in the worst case.
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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node once. |
| 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) | — |
| 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 |
N-ary Tree Preorder Traversal | Live Coding with Explanation | Leetcode - 589 • Algorithms Made Easy • 12,575 views views
Watch 9 more video solutions →Practice N-ary Tree Preorder Traversal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor