N-ary Tree Preorder Traversal - Practice Coding Problems

N-ary Tree Preorder Traversal - 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).

Preorder traversal visits nodes in the order: current node → left subtree → right subtree (for binary trees), or current node → all children from left to right (for n-ary trees).

Input & Output

Example 1 — Basic N-ary Tree

$ Input: root = [1,null,3,2,4,null,5,6]

› Output: [1,3,5,6,2,4]

💡 Note: Start at root 1, then visit child 3 and its children 5,6, then visit remaining children 2,4 of root

Example 2 — Complex Tree

$ 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]

💡 Note: Preorder traversal visits each node before exploring its subtree

Example 3 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Tree with only root node returns array with single element

Constraints

The number of nodes in the tree is in the range [0, 10⁴]
0 ≤ Node.val ≤ 10⁴
The height of the n-ary tree is less than or equal to 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

N-ary tree with nodes [1,null,3,2,4,null,5,6]

Preorder Visit

Visit root first, then each subtree recursively

Result Array

Nodes in order visited: [1,3,5,6,2,4]

Key Takeaway

🎯 Key Insight: Preorder traversal processes the current node before recursively visiting all its children from left to right.

Asked in

M Microsoft 35 a Amazon 28 G Google 22 f Facebook 18

N-ary tree preorder traversal visits nodes in root-first order. The key insight is processing the current node before its children. Both recursive DFS and iterative stack approaches work optimally. Time: O(n), Space: O(h) for recursion or O(w) for stack where h is height and w is maximum width.

Common Approaches

Approach	Time	Space	Notes
✓ Iterative Stack	O(n)	O(w)	Use a stack to simulate recursion iteratively
Recursive DFS	O(n)	O(h)	Use recursion to visit current node then all children

Iterative Stack — Algorithm Steps

Push root to stack
While stack not empty: pop node, add to result, push children in reverse order

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Root

Start with root 1 in stack

Pop and Process

Pop 1, add to result, push children 4,2,3 (reverse order)

Continue

Pop 3, add to result, push children 6,5

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    int val;
    struct Node** children;
    int numChildren;
};

struct Node* createNode(int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->val = val;
    node->children = NULL;
    node->numChildren = 0;
    return node;
}

int* solution(struct Node* root, int* returnSize) {
    *returnSize = 0;
    if (!root) return NULL;
    
    int* result = (int*)malloc(10000 * sizeof(int));
    struct Node** stack = (struct Node**)malloc(10000 * sizeof(struct Node*));
    int stackSize = 0;
    
    stack[stackSize++] = root;
    
    while (stackSize > 0) {
        struct Node* node = stack[--stackSize];
        result[(*returnSize)++] = node->val;
        
        // Add children in reverse order
        for (int i = node->numChildren - 1; i >= 0; i--) {
            stack[stackSize++] = node->children[i];
        }
    }
    
    free(stack);
    return result;
}

int main() {
    // For simplicity, create a basic test case
    struct Node* root = createNode(1);
    root->children = (struct Node**)malloc(3 * sizeof(struct Node*));
    root->numChildren = 3;
    root->children[0] = createNode(3);
    root->children[1] = createNode(2);
    root->children[2] = createNode(4);
    
    root->children[0]->children = (struct Node**)malloc(2 * sizeof(struct Node*));
    root->children[0]->numChildren = 2;
    root->children[0]->children[0] = createNode(5);
    root->children[0]->children[1] = createNode(6);
    
    int returnSize;
    int* result = solution(root, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once

✓ Linear Growth

Space Complexity

O(w)

Stack holds at most w nodes where w is maximum width of tree

✓ Linear Space

182.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Iterative Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler