N-ary Tree Postorder Traversal - Practice Coding Problems

N-ary Tree Postorder Traversal - Problem

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

N-ary tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (see examples).

In postorder traversal, we visit all children nodes first, then the parent node.

Input & Output

Example 1 — Basic N-ary Tree

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

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

💡 Note: Postorder visits children first: node 3's children [5,6], then node 3, then nodes 2,4, finally root 1

Example 2 — Deeper 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: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

💡 Note: Complex tree with multiple levels - each subtree processed before its parent

Example 3 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Single node tree returns just that node's value

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 root 1 and children [3,2,4], where 3 has children [5,6]

Traversal Order

Visit children first: 5,6 → 3 → 2,4 → 1

Result

Postorder sequence: [5,6,3,2,4,1]

Key Takeaway

🎯 Key Insight: Postorder means 'children first, parent last' - perfect for bottom-up tree processing

Asked in

F Facebook 15 G Google 12 a Amazon 8 M Microsoft 6

The key insight is that postorder traversal visits children before the parent node. The recursive DFS approach naturally follows this pattern by processing all children recursively before adding the current node to the result. Time: O(n), Space: O(n) for recursion stack and result array.

Common Approaches

Approach	Time	Space	Notes
✓ Iterative with Stack	O(n)	O(n)	Use stack to simulate recursion and avoid stack overflow
Recursive DFS	O(n)	O(n)	Recursively visit all children first, then process current node

Iterative with Stack — Algorithm Steps

Push root to stack
Pop node, add to result stack, push children to traversal stack
Pop from result stack to get postorder

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Root

Add root node 1 to stack

Process & Push Children

Pop node, add to result, push children

Reverse Result

Reverse final array for postorder

Code -

solution.c — C

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

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

struct Node** stack;
int stackSize;
int* result;
int resultSize;

int* solution(struct Node* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    stack = (struct Node**)malloc(10000 * sizeof(struct Node*));
    result = (int*)malloc(10000 * sizeof(int));
    stackSize = 0;
    resultSize = 0;
    
    stack[stackSize++] = root;
    
    while (stackSize > 0) {
        struct Node* node = stack[--stackSize];
        result[resultSize++] = node->val;
        
        // Add children to stack (left to right for postorder)
        for (int i = 0; i < node->numChildren; i++) {
            stack[stackSize++] = node->children[i];
        }
    }
    
    // Reverse to get postorder (children before parent)
    for (int i = 0; i < resultSize / 2; i++) {
        int temp = result[i];
        result[i] = result[resultSize - 1 - i];
        result[resultSize - 1 - i] = temp;
    }
    
    *returnSize = resultSize;
    return result;
}

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

int main() {
    // Simplified input parsing for basic case
    struct Node* root = createNode(1);
    struct Node* child1 = createNode(3);
    struct Node* child2 = createNode(2);
    struct Node* child3 = createNode(4);
    
    root->children = (struct Node**)malloc(3 * sizeof(struct Node*));
    root->children[0] = child1;
    root->children[1] = child2;
    root->children[2] = child3;
    root->numChildren = 3;
    
    child1->children = (struct Node**)malloc(2 * sizeof(struct Node*));
    child1->children[0] = createNode(5);
    child1->children[1] = createNode(6);
    child1->numChildren = 2;
    
    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");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once

✓ Linear Growth

Space Complexity

O(n)

Two stacks can hold up to n nodes total

⚡ Linearithmic Space

186.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 with Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler