N-ary Tree Postorder Traversal

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?

Approach: Iterative with Two Stacks (Reverse Preorder)

Algorithm

1. Postorder visits all children of a node (left to right) and then the node itself
2. Process a “root, children” preorder traversal but push values into an output stack, pushing children in their natural (left-to-right) order
3. When the first stack is empty, pop everything from the output stack
4. Because of the LIFO order of the output stack, the stored sequence is reversed into the proper postorder
5. The result is children-before-parent for every subtree

Time & Space Complexity

• Time Complexity: O(n) - every node is processed once
• Space Complexity: O(n) - the two stacks can hold up to O(n) nodes in the worst case

Java Implementation

import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;

public class NaryTreePostorderTraversal {

    public static List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<Node> stack = new ArrayDeque<>();
        Deque<Integer> output = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            output.push(node.val);
            for (Node child : node.children) {
                stack.push(child);
            }
        }

        while (!output.isEmpty()) {
            result.add(output.pop());
        }
        return result;
    }

    public static class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int val) {
            this.val = val;
        }

        public Node(int val, List<Node> children) {
            this.val = val;
            this.children = children;
        }
    }

    // Test method
    public static void main(String[] args) {
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n3 = new Node(3, new ArrayList<>(List.of(n5, n6)));
        Node n2 = new Node(2);
        Node n4 = new Node(4);
        Node root = new Node(1, new ArrayList<>(List.of(n3, n2, n4)));

        System.out.println("Input: root = [1,null,3,2,4,null,5,6]");
        System.out.println("Output: " + postorder(root)); // Expected: [5, 6, 3, 2, 4, 1]
    }
}

Recursive Implementation

public List<Integer> postorderRecursive(Node root) {
    List<Integer> result = new ArrayList<>();
    helper(root, result);
    return result;
}

private void helper(Node node, List<Integer> result) {
    if (node == null) {
        return;
    }
    for (Node child : node.children) {
        helper(child, result);
    }
    result.add(node.val);
}

Example Walkthrough

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

1. Pop 1, push into output, push children 3, 2, 4 (top is 4)
2. Pop 4, push into output, no children. Pop 2, push into output
3. Pop 3, push into output, push children 5, 6 (top is 6)
4. Pop 6, push into output; pop 5, push into output
5. Output stack holds [5, 6, 3, 2, 4, 1] top-down; popping yields [5, 6, 3, 2, 4, 1]

Key Points

1. Children Before Parent: A node is emitted only after all of its descendants
2. Reverse Preorder Trick: Storing a “root, children” traversal on a second stack reverses it into postorder
3. Natural Child Push Order: Pushing children left to right makes the last child pop first, which the output stack then fixes
4. n-ary vs Binary: The technique generalizes the binary two-stack postorder to arbitrary child counts
5. O(n) Time: Every node is visited exactly once