Beats 100% | 2 Solutions
\n\n# Intuition\nThe task is to perform postorder traversal on an N-ary tree. In postorder traversal, we visit all the children of a node first, then the node i
![image.png](https://assets.leetcode.com/users/images/d2514ff7-b69d-463c-a56b-533917f68454_1724654682.922908.png)\n\n# Intuition\nThe task is to perform postorder traversal on an N-ary tree. In postorder traversal, we visit all the children of a node first, then the node itself. This is similar to postorder traversal in a binary tree but adapted for N-ary trees, where each node can have multiple children.\n\n# Solution 1: Recursive Approach\n\n1. The most straightforward way to perform postorder traversal is using recursion.\n2. We recursively traverse all children of the current node, and once we\u2019ve visited all children, we add the node\u2019s value to the result list.\n3. This mirrors the definition of postorder traversal: first process all children, then the node.\n# Solution 2: Iterative Approach Using Stack\n\n1. This approach simulates the recursive postorder traversal using a stack.\n2. We push nodes into the stack and process them iteratively. When we encounter a node, we push its children onto the stack in reverse order (so that the leftmost child is processed first).\n3. Once all the children of a node are processed, the node itself is added to the result list.\n# Complexities:\n- Solution 1: Recursive Approach\n\n    - Time Complexity: O(N) \u2014 We visit every node once.\n    - Space Complexity: O(H) \u2014 The recursion stack can go as deep as the height of the tree (H).\n- Solution 2: Iterative Approach Using Stack\n\n    - Time Complexity: O(N) \u2014 We process every node once.\n    - Space Complexity: O(N) \u2014 The stack will store the nodes, and in the worst case, it will hold all the nodes of the tree.\n\n# Code - 1\n```cpp []\nclass Solution {\nprivate:\n    void helper(Node * n,vector<int> &res){\n        if(n == NULL) return;\n        for(auto c : n->children){\n            helper(c,res);\n        }\n        res.push_back(n->val);\n    }\npublic:\n    vector<int> postorder(Node* root) {\n        vector<int> res;\n        helper(root,res);\n        return res;\n    }\n};\n```\n```Java []\nclass Solution {\n    public void helper(Node root, List<Integer> res) {\n        if (root == null) return;\n        for (Node child : root.children) {\n            helper(child, res);\n        }\n        res.add(root.val);\n    }\n\n    public List<Integer> postorder(Node root) {\n        List<Integer> res = new ArrayList<>();\n        helper(root, res);\n        return res;\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def helper(self, root: \'Node\', res: List[int]) -> None:\n        if root is None:\n            return\n        for child in root.children:\n            self.helper(child, res)\n        res.append(root.val)\n\n    def postorder(self, root: \'Node\') -> List[int]:\n        res = []\n        self.helper(root, res)\n        return res\n\n```\n```Javascript []\nvar postorder = function(root) {\n    const res = [];\n    const helper = (node) => {\n        if (!node) return;\n        for (let child of node.children) {\n            helper(child);\n        }\n        res.push(node.val);\n    };\n    helper(root);\n    return res;\n};\n\n```\n# Code - 2\n```C++ []\nclass Solution {\npublic:\n    vector<int> postorder(Node* root) {\n        if(!root) return {};\n        vector<int> res;\n\n        stack<Node * > st;\n        st.push(root);\n        Node * temp;\n        while(!st.empty()){\n            temp = st.top();\n\n            if(temp->children.size() == 0){\n                res.push_back(temp->val);\n                st.pop();\n            }\n            while(temp->children.size() > 0){\n                st.push(temp->children.back());\n                temp->children.pop_back();\n            }\n        }\n        return res;\n    }\n};\n```\n```Java []\nclass Solution {\n    public List<Integer> postorder(Node root) {\n        if (root == null) return new ArrayList<>();\n        List<Integer> res = new ArrayList<>();\n        Stack<Node> stack = new Stack<>();\n        stack.push(root);\n\n        while (!stack.isEmpty()) {\n            Node temp = stack.pop();\n            res.add(0, temp.val); // Add node at the beginning to reverse the postorder sequence\n            for (Node child : temp.children) {\n                stack.push(child);\n            }\n        }\n        return res;\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def postorder(self, root: \'Node\') -> List[int]:\n        if root is None:\n            return []\n        res, stack = [], [root]\n        \n        while stack:\n            temp = stack.pop()\n            res.insert(0, temp.val)  # Insert at the beginning to reverse postorder sequence\n            stack.extend(temp.children)\n        \n        return res\n\n```\n```Javascript []\nvar postorder = function(root) {\n    if (!root) return [];\n    const res = [];\n    const stack = [root];\n    \n    while (stack.length > 0) {\n        const temp = stack.pop();\n        res.unshift(temp.val);  // Add at the beginning to reverse the postorder sequence\n        for (let child of temp.children) {\n            stack.push(child);\n        }\n    }\n    return res;\n};\n\n```\n![Please hit the upvote button (1).png](https://assets.leetcode.com/users/images/87d7c7b5-7655-46b3-908f-5f1f65e6f563_1724654528.9151871.png)\n
['Stack', 'Tree', 'Depth-First Search', 'C++', 'Java', 'Python3', 'JavaScript']