Scale Engineer

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
StackTree

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, 104].
  • 0 <= Node.val <= 104
  • 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. 
  • Iterate 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.
/*// 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> result = new LinkedList<>();        if (root == null) {            return result;        }         Stack<Node> stack = new Stack<>();        stack.push(root);         while (!stack.isEmpty()) {            Node node = stack.pop();            // Add to the front of the list            result.addFirst(node.val);             // Push children from left to right, so they are processed from right to left            for (Node child : node.children) {                stack.push(child);            }        }        return result;    }}

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.

Solutions

/* // 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 ; } }

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 →

Next problem