# N-ary Tree Postorder Traversal

`Tree`

**Easy**

Given an n-ary tree, return thepostordertraversal of its nodes' values.

For example, given a`3-ary`tree:

![](https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png)

Return its postorder traversal as:`[5,6,3,2,4,1]`.

**Note:**

Recursive solution is trivial, could you do it iteratively?

## Solution

### Iterative - with stack

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        LinkedList<Node> stack = new LinkedList<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.addFirst(node.val);

            if (node.children != null) {
                for (Node c: node.children) {
                    if (c != null) {
                        stack.push(c);
                    }
                }
            }
        }

        return res;
    }
}
```

**Complexity Analysis**

* Time complexity : we visit each node exactly once, thus the time complexity is O(N), where N is the number of nodes, \_i.e.\_ the size of tree.
* Space complexity : depending on the tree structure, we could keep up to the entire tree, therefore, the space complexity is O(N).

### Recursive

```java
class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }

        postorderHelper(root, res);

        return res;
    }

    private void postorderHelper(Node root, List<Integer> res) {
        if (root == null) {
            return;
        }
        if (root.children != null) {
            for (Node c : root.children) {
                postorderHelper(c, res);
            }
        }
        res.add(root.val);
    }
}
```