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?
The goal of preorder traversal in an N-ary tree is to visit the root node first, then recursively process each of its children from left to right. Because each node can have multiple children (unlike binary trees), the traversal simply extends the classic preorder DFS idea to a list of children.
A common approach is Depth-First Search (DFS) using recursion. Start at the root, record its value, and recursively traverse each child in order. This method is simple and closely follows the natural definition of preorder traversal.
An alternative is an iterative solution using a stack. Push the root node onto the stack, process it, and push its children in reverse order so they are visited in the correct left-to-right sequence. Both approaches ensure every node is visited exactly once.
The time complexity is O(n) since every node is processed once, while the space complexity depends on recursion depth or stack usage, which can reach O(h) where h is the tree height.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive DFS | O(n) | O(h) |
| Iterative DFS using Stack | O(n) | O(h) |
NeetCode
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4// Definition for a Node.
5struct Node {
6 int val;
7 int numChildren;
8 struct Node** children;
9};
10
11void preorderHelper(struct Node* node, int* returnArray, int* returnSize) {
12 if (node == NULL) return;
13 returnArray[(*returnSize)++] = node->val;
14 for (int i = 0; i < node->numChildren; i++) {
15 preorderHelper(node->children[i], returnArray, returnSize);
16 }
17}
18
19int* preorder(struct Node* root, int* returnSize) {
20 *returnSize = 0;
21 int* returnArray = malloc(10000 * sizeof(int)); // Assuming max size
22 preorderHelper(root, returnArray, returnSize);
23 return returnArray;
24}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.
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.
Time Complexity: O(n). Space Complexity: O(n), as most nodes can be stored in the stack in the worst case.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, tree traversal problems like N-ary Tree Preorder Traversal are common in technical interviews, including FAANG companies. They test your understanding of tree structures, recursion, and DFS traversal strategies.
A stack is commonly used for the iterative DFS approach. It helps simulate the recursion process and ensures nodes are processed in preorder. When pushing children onto the stack, they are typically added in reverse order to maintain the correct traversal sequence.
The optimal approach is Depth-First Search (DFS), either recursively or using an explicit stack. Both methods visit the root first and then traverse all children from left to right. Each node is processed exactly once, resulting in O(n) time complexity.
In a binary tree, each node has at most two children (left and right), so preorder processes root, left, then right. In an N-ary tree, a node can have multiple children, so preorder processes the root and then iterates through all children from left to right.
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.