# N-ary Tree Postorder Traversal
**Difficulty:** EASY
[External](https://leetcode.com/problems/n-ary-tree-postorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/n-ary-tree-postorder-traversal
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Stack, Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/n-ary-tree-postorder-traversal/image0.png) 

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

**Example 2:**

![](https://assets.glich.co/dsa/n-ary-tree-postorder-traversal/image1.png) 

**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
## Recursive Approach
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.
**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.
**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.
### Explanation
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.
```java
/*
// 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) {
        List<Integer> result = new ArrayList<>();
        helper(root, result);
        return result;
    }

    private void helper(Node node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // 1. Traverse all children
        for (Node child : node.children) {
            helper(child, result);
        }
        // 2. Visit the root
        result.add(node.val);
    }
}
```
### 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)`.

## Iterative Approach using a Stack
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.
**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).
**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.
### Explanation
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`.
```java
/*
// 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.
### 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.

# Solutions
### Java

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

### CPP

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

### Python

```python
""" # 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 ]
```