N-ary Tree Postorder Traversal

Easy

#0562Time: O(N), where N is the total number of nodes. Each node is pushed onto and popped from the stack exactly once.Space: O(W), where W is the maximum width of the tree. In the worst case of a complete N-ary tree, the last level can contain roughly O(N) nodes. Therefore, the worst-case space complexity is O(N).

Algorithms

Depth-First Search

Data structures

Stack Tree

Prompt

Given the root of an n-ary tree, return the postorder 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: [5,6,3,2,4,1]

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

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.

Follow up: Recursive solution is trivial, could you do it iteratively?

Approaches

2 approaches with complexity analysis and trade-offs.

An iterative solution avoids recursion and the risk of stack overflow. A common and elegant iterative technique for postorder traversal involves using a single stack and modifying the preorder traversal logic. The standard preorder traversal is (Root, Left, Right). We can modify it to (Root, Right, Left) and then reverse the result to get (Left, Right, Root), which is the postorder traversal.

Algorithm

Initialize an empty LinkedList<Integer> named result and an empty Stack<Node> named stack.
If root is null, return the empty result.
Push the root node onto the stack.
Loop while the stack is not empty:
Pop a node, `current`, from the `stack`.
Add `current.val` to the *front* of the `result` list.

1Iterate through the children of `current` from left to right and push each `child` onto the `stack`.

Return the result list.

Walkthrough

For an N-ary tree, the modified preorder traversal becomes (Root, Last Child, ..., First Child).

We initialize a stack and push the root node onto it.
We also initialize a LinkedList for our result. Using a LinkedList allows for efficient O(1) additions to the front.
We loop as long as the stack is not empty. In each iteration:
1. We pop a node from the stack.
2. We add this node's value to the front of our result list. This is the key step that achieves the reversal.
3. We then iterate through the children of the popped node (from left to right) and push them onto the stack. Because the stack is a LIFO (Last-In, First-Out) structure, the last child pushed (the rightmost one) will be on top and will be processed next.
This process effectively traverses the tree in the order of Root, Child_N, ..., Child_1 and builds the result list in reverse, yielding the correct postorder sequence Child_1, ..., Child_N, Root.

1/*2// Definition for a Node.3class Node {4    public int val;5    public List<Node> children;6 7    public Node() {}8 9    public Node(int _val) {10        val = _val;11    }12 13    public Node(int _val, List<Node> _children) {14        val = _val;15        children = _children;16    }17};18*/19 20class Solution {21    public List<Integer> postorder(Node root) {22        LinkedList<Integer> result = new LinkedList<>();23        if (root == null) {24            return result;25        }26 27        Stack<Node> stack = new Stack<>();28        stack.push(root);29 30        while (!stack.isEmpty()) {31            Node node = stack.pop();32            // Add to the front of the list33            result.addFirst(node.val);34 35            // Push children from left to right, so they are processed from right to left36            for (Node child : node.children) {37                stack.push(child);38            }39        }40        return result;41    }42}

If using an ArrayList, you would add to the end and then reverse the entire list once at the end using Collections.reverse(result). Adding to the front of a LinkedList is generally more efficient.

Complexity

Time

O(N), where N is the total number of nodes. Each node is pushed onto and popped from the stack exactly once.

Space

O(W), where W is the maximum width of the tree. In the worst case of a complete N-ary tree, the last level can contain roughly O(N) nodes. Therefore, the worst-case space complexity is O(N).

Trade-offs

Pros

Avoids recursion, eliminating the risk of stack overflow.
Can be slightly more memory efficient by using heap memory (for the stack) instead of the call stack.

Cons

The logic is less direct and intuitive compared to the recursive solution.

The most intuitive way to perform a postorder traversal is using recursion. The definition of postorder traversal is to traverse all the children subtrees before visiting the root node itself. A recursive function naturally models this 'visit after' behavior.

Algorithm

Create a helper function traverse(node, resultList).
If the node is null, return.
Iterate through each child in the node.children list.
For each child, make a recursive call: traverse(child, resultList).
After the loop finishes, add the current node.val to the resultList.
In the main function, initialize an empty list and call traverse(root, resultList).

Walkthrough

We define a helper function that takes a node and a list to store the results.

The base case for the recursion is when the current node is null.
For the current non-null node, we first iterate through its list of children. For each child, we make a recursive call. This ensures that all nodes in the children's subtrees are visited and added to the result list first.
After the loop over the children completes, we add the value of the current node to the result list.
The main function initializes an empty list and calls this recursive helper function with the root of the tree.

1/*2// Definition for a Node.3class Node {4    public int val;5    public List<Node> children;6 7    public Node() {}8 9    public Node(int _val) {10        val = _val;11    }12 13    public Node(int _val, List<Node> _children) {14        val = _val;15        children = _children;16    }17};18*/19 20class Solution {21    public List<Integer> postorder(Node root) {22        List<Integer> result = new ArrayList<>();23        helper(root, result);24        return result;25    }26 27    private void helper(Node node, List<Integer> result) {28        if (node == null) {29            return;30        }31        // 1. Traverse all children32        for (Node child : node.children) {33            helper(child, result);34        }35        // 2. Visit the root36        result.add(node.val);37    }38}

Complexity

Time

O(N), where N is the total number of nodes in the tree. Each node is visited exactly once.

Space

O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst-case scenario of a skewed tree (like a linked list), the height H can be equal to N, leading to O(N) space complexity.

Trade-offs

Pros

Simple and intuitive to write.
The code directly reflects the definition of postorder traversal.

Cons

May cause a stack overflow for very deep trees, although the problem constraints (height <= 1000) make this less of a concern.
Recursive calls can have higher overhead than an iterative approach.

Solutions

Solution

1/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List < Integer > postorder ( Node root ) { LinkedList < Integer > ans = new LinkedList <>(); if ( root == null ) { return ans ; } Deque < Node > stk = new ArrayDeque <>(); stk . offer ( root ); while (! stk . isEmpty ()) { root = stk . pollLast (); ans . addFirst ( root . val ); for ( Node child : root . children ) { stk . offer ( child ); } } return ans ; } }

1/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: vector < int > postorder ( Node * root ) { vector < int > ans ; if ( ! root ) return ans ; stack < Node *> stk { { root } }; while ( ! stk . empty ()) { root = stk . top (); ans . push_back ( root -> val ); stk . pop (); for ( Node * child : root -> children ) stk . push ( child ); } reverse ( ans . begin (), ans . end ()); return ans ; } };

1""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution : def postorder ( self , root : 'Node' ) -> List [ int ]: ans = [] if root is None : return ans stk = [ root ] while stk : node = stk . pop () ans . append ( node . val ) for child in node . children : stk . append ( child ) return ans [:: - 1 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem