Recursive Approach gave O(N) Beats 100 % | 0 - ms
Intuition\n\nTry to understand the fundamental difference between postorder traversal and other types of tree traversal, such as preorder or inorder. In postord
### Intuition\n\nTry to understand the fundamental difference between postorder traversal and other types of tree traversal, such as preorder or inorder. In postorder traversal, the order of visit is important \u2013 we must first visit all the children of a node before visiting the node itself. This bottom-up approach is the opposite of preorder traversal, where we visit the node first and then its children. The postorder traversal starts from the leaf nodes and gradually works the way up to the root.\nNow Trees, by their very definition, are recursively defined \u2013 each node in a tree can be seen as the root of a smaller subtree. This recursive structure suggests that we can tackle the problem by breaking down the larger tree into smaller, more manageable subproblems i.e by processing the children of a node before the node itself, we can naturally capture the postorder traversal order. \n\n\nIn short:\n- For any node, you should first traverse all of its children. This means you need to visit each subtree rooted at the children before processing the current node.\n- After you have visited all of the children you then add the value of the current node itself to the result.\n```\n        1\n       /|\\\n      3 2 4\n     / \\\n    5   6\n```\nInput: root = [1,null,3,2,4,null,5,6]\nUnderstand it like this \n\nvist 1 explore its children - 3,2,4\n\nvisit 3 explore its childern -5,6\n\nvisit 5 no children to explore (add 5 to traversal)\n\nvisit 6 no children to explore ( add 6 to traversal)\n\nvisit 3 no children left to explore (add 3 to traversal)\n\nvisit 2 no children to explore (add 3 to traversla )\n\nvisit 4 no children to explore (add 4 to travesal)\n\nOutput: [5,6,3,2,4,1]\n### Approach\n\n\n\nMy approach to solving this is:\n\n1. **Initialization**:\n   - We start by initializing an empty `result` list to store the postorder traversal of the n-ary tree.\n   - This `result` list will store the values of the nodes in the correct postorder sequence.\n\n2. **Base Case**:\n   - We define a base case for the recursion: if the `root` node is `null`, we simply return the empty `result` list, as there is nothing to traverse.\n\n3. **Recursive Traversal Function**:\n   - We define a helper function called `traverse` that performs the recursive postorder traversal.\n   - The `traverse` function takes two parameters: the current `node` being processed and the `result` list to store the traversal.\n\n4. **Recursive Exploration of Children**:\n   - Inside the `traverse` function, we first recursively call the `traverse` function on each child of the current `node`.\n   - By recursively calling `traverse` on each child, we ensure that we visit all the children of the current `node` from left to right before visiting the `node` itself. This aligns with the postorder traversal order.\n\n5. **Adding Node Value**:\n   - After all the children have been visited, we add the current `node`\'s value to the `result` list.\n   - This step ensures that the node\'s value is only added to the result after all its descendants have been processed, following the postorder traversal principle.\n\n6. **Initiating the Traversal**:\n   - To start the postorder traversal, we call the `traverse` function with the `root` node and the `result` list as arguments.\n\n7. **Returning the Result**:\n   - Once the recursive traversal is complete, the `result` list contains the postorder traversal sequence, which we return as the final output.\n\nThe pseudocode for this approach can be summarized as follows:\n\n```pseudo\nfunction postorder(root):\n    result = empty list\n    if root is null:\n        return result\n    traverse(root, result)\n    return result\n\nfunction traverse(node, result):\n    for each child in node.children:\n        traverse(child, result)\n    result.add(node.val)\n```\n\n\n\n\n\n### Complexity Analysis\n\n **Time Complexity $O(N)$**\nThe time complexity of this solution is **O(N)**, where N is the total number of nodes in the n-ary tree Because:\n\n1. We visit each node exactly once during the postorder traversal. The recursive calls to the `traverse` function ensure that we explore the entire depth of each subtree before moving on to the next sibling subtree.\n2. The loop that iterates over the children of each node has a time complexity of O(k), where k is the number of children for the current node. However, since the sum of the number of children for all nodes in the tree is equal to N (the total number of nodes), the overall time complexity remains O(N).\n3. The constant-time operations, such as adding a value to the `result` list, do not contribute significantly to the overall time complexity.\n\n\n\n **Space Complexity $O(N)$**\nThe space complexity of this solution is also **O(N)**, where N is the total number of nodes in the n-ary tree Because:\n\n1. We need to store the result of the postorder traversal in the `result` list. In the worst case, the n-ary tree could be a linear structure (i.e., each node has only one child), in which case the depth of the recursion would be N, and we would need to store N values in the `result` list.\n2. The space used for the function call stack during the recursive calls is proportional to the depth of the tree, which is O(N) in the worst case.\n3. Apart from the `result` list and the function call stack, the solution does not require any additional data structures that would contribute significantly to the space complexity.\n\n\n\n\n\n### Code\n```java []\npublic class Solution {\n    public List<Integer> postorder(Node root) {\n        List<Integer> result = new ArrayList<>();\n        if (root != null) {\n            traverse(root, result);\n        }\n        return result;\n    }\n    private void traverse(Node node, List<Integer> result) {\n        for (Node child : node.children) {\n            traverse(child, result);\n        }\n        result.add(node.val);\n    }\n}\n\n```\n\n```C++ []\nclass Solution {\npublic:\n    vector<int> postorder(Node* root) {\n        vector<int> result;\n        if (root != nullptr) {\n            traverse(root, result);\n        }\n        return result;\n    }\n\nprivate:\n    void traverse(Node* node, vector<int>& result) {\n        for (auto* child : node->children) {\n            traverse(child, result);\n        }\n        result.push_back(node->val);\n    }\n};\n\n```\n```C# []\npublic class Solution {\n    public IList<int> Postorder(Node root) {\n        List<int> result = new List<int>();\n        if (root != null) {\n            Traverse(root, result);\n        }\n        return result;\n    }\n\n    private void Traverse(Node node, List<int> result) {\n        foreach (var child in node.children) {\n            Traverse(child, result);\n        }\n        result.Add(node.val);\n    }\n}\n\n\n```\n```Python []\nclass Solution:\n    def postorder(self, root: \'Node\') -> List[int]:\n        result = []\n        if root:\n            self.traverse(root, result)\n        return result\n\n    def traverse(self, node: \'Node\', result: List[int]):\n        for child in node.children:\n            self.traverse(child, result)\n        result.append(node.val)\n\n\n```\n```kotlin []\nclass Solution {\n    fun postorder(root: Node?): List<Int> {\n        val result = mutableListOf<Int>()\n        if (root != null) {\n            traverse(root, result)\n        }\n        return result\n    }\n\n    private fun traverse(node: Node, result: MutableList<Int>) {\n        for (child in node.children) {\n            child?.let { traverse(it, result) }\n        }\n        result.add(node.`val`)\n    }\n}\n\n\n```\n```Go []\nfunc postorder(root *Node) []int {\n    result := []int{}\n    if root != nil {\n        traverse(root, &result)\n    }\n    return result\n}\n\nfunc traverse(node *Node, result *[]int) {\n    for _, child := range node.Children {\n        traverse(child, result)\n    }\n    *result = append(*result, node.Val)\n}\n\n\n```\n```JavaScript []\n/**\n * @param {_Node|null} root\n * @return {number[]}\n */\nvar postorder = function(root) {\n    const result = [];\n    if (root !== null) {\n        traverse(root, result);\n    }\n    return result;\n};\n\nfunction traverse(node, result) {\n    for (const child of node.children) {\n        traverse(child, result);\n    }\n    result.push(node.val);\n}\n\n\n```\n```TypeScript []\nfunction postorder(root: _Node | null): number[] {\n    const result: number[] = [];\n    if (root !== null) {\n        traverse(root, result);\n    }\n    return result;\n}\n\nfunction traverse(node: _Node, result: number[]): void {\n    for (const child of node.children) {\n        traverse(child, result);\n    }\n    result.push(node.val);\n}\n\n\n```\n```Rust []\nimpl Solution {\n    pub fn postorder(root: Option<Rc<RefCell<Node>>>) -> Vec<i32> {\n        let mut result = Vec::new();\n        if let Some(node) = root {\n            Self::traverse(&node, &mut result);\n        }\n        result\n    }\n\n    fn traverse(node: &Rc<RefCell<Node>>, result: &mut Vec<i32>) {\n        for child in node.borrow().children.iter() {\n            Self::traverse(child, result);\n        }\n        result.push(node.borrow().val);\n    }\n}\n\n\n```\n---\n\n\n### Example 1\n\n**Input:** `root = [1,null,3,2,4,null,5,6]`\n\n**Tree Structure:**\n```\n        1\n       /|\\\n      3 2 4\n     / \\\n    5   6\n```\n\n\n**Dry Run:**\n\n1. **Initialize:**\n   - Call `postorder(root)` with `root` being the node with value `1`.\n   - Initialize `result` as an empty list: `result = []`.\n\n2. **Start Traversal:**\n   - Call `traverse(root, result)` with `node = 1`.\n\n3. **Traverse Node 1:**\n   - Node `1` has children `[3, 2, 4]`.\n\n4. **Traverse Child 3:**\n   - Call `traverse(3, result)`.\n   - Node `3` has children `[5, 6]`.\n\n5. **Traverse Child 5 of Node 3:**\n   - Call `traverse(5, result)`.\n   - Node `5` has no children.\n   - Add `5` to `result`: `result = [5]`.\n   - Return to the previous call (Node `3`).\n\n6. **Traverse Child 6 of Node 3:**\n   - Call `traverse(6, result)`.\n   - Node `6` has no children.\n   - Add `6` to `result`: `result = [5, 6]`.\n   - Return to the previous call (Node `3`).\n\n7. **Complete Node 3 Traversal:**\n   - Add `3` to `result` after processing all its children: `result = [5, 6, 3]`.\n   - Return to the previous call (Node `1`).\n\n8. **Traverse Node 2:**\n   - Call `traverse(2, result)`.\n   - Node `2` has no children.\n   - Add `2` to `result`: `result = [5, 6, 3, 2]`.\n   - Return to the previous call (Node `1`).\n\n9. **Traverse Node 4:**\n   - Call `traverse(4, result)`.\n   - Node `4` has no children.\n   - Add `4` to `result`: `result = [5, 6, 3, 2, 4]`.\n   - Return to the previous call (Node `1`).\n\n10. **Complete Node 1 Traversal:**\n    - Add `1` to `result` after processing all its children: `result = [5, 6, 3, 2, 4, 1]`.\n\n11. **Return Result:**\n    - The final output of the traversal is `[5, 6, 3, 2, 4, 1]`.\n\n### Example 2\n\n**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]`\n\n**Tree Structure:**\n```\n        1\n     / |   \\  \\\n    /  |    \\  \\\n    2  3     4  5\n      /|     |  | \\\n     6 7     8  9 10\n       |     |  |\n       11    12 13\n       |        \n       14       \n```\n\n\n\n\n**Dry Run:**\n\n1. **Initialize:**\n   - Call `postorder(root)` with `root` being the node with value `1`.\n   - Initialize `result` as an empty list: `result = []`.\n\n2. **Start Traversal:**\n   - Call `traverse(root, result)` with `node = 1`.\n\n3. **Traverse Node 1:**\n   - Node `1` has children `[2, 3, 4, 5]`.\n\n4. **Traverse Child 2 of Node 1:**\n   - Call `traverse(2, result)`.\n   - Node `2` has no children.\n   - Add `2` to `result`: `result = [2]`.\n   - Return to the previous call (Node `1`).\n\n5. **Traverse Child 3 of Node 1:**\n   - Call `traverse(3, result)`.\n   - Node `3` has children `[6, 7]`.\n\n6. **Traverse Child 6 of Node 3:**\n   - Call `traverse(6, result)`.\n   - Node `6` has no children.\n   - Add `6` to `result`: `result = [2, 6]`.\n   - Return to the previous call (Node `3`).\n\n7. **Traverse Child 7 of Node 3:**\n   - Call `traverse(7, result)`.\n   - Node `7` has children `[11]`.\n\n8. **Traverse Child 11 of Node 7:**\n   - Call `traverse(11, result)`.\n   - Node `11` has children `[14]`.\n\n9. **Traverse Child 14 of Node 11:**\n   - Call `traverse(14, result)`.\n   - Node `14` has no children.\n   - Add `14` to `result`: `result = [2, 6, 14]`.\n   - Return to the previous call (Node `11`).\n\n10. **Complete Node 11 Traversal:**\n    - Add `11` to `result`: `result = [2, 6, 14, 11]`.\n    - Return to the previous call (Node `7`).\n\n11. **Complete Node 7 Traversal:**\n    - Add `7` to `result`: `result = [2, 6, 14, 11, 7]`.\n    - Return to the previous call (Node `3`).\n\n12. **Complete Node 3 Traversal:**\n    - Add `3` to `result`: `result = [2, 6, 14, 11, 7, 3]`.\n    - Return to the previous call (Node `1`).\n\n13. **Traverse Child 4 of Node 1:**\n    - Call `traverse(4, result)`.\n    - Node `4` has children `[8]`.\n\n14. **Traverse Child 8 of Node 4:**\n    - Call `traverse(8, result)`.\n    - Node `8` has children `[12]`.\n\n15. **Traverse Child 12 of Node 8:**\n    - Call `traverse(12, result)`.\n    - Node `12` has no children.\n    - Add `12` to `result`: `result = [2, 6, 14, 11, 7, 3, 12]`.\n    - Return to the previous call (Node `8`).\n\n16. **Complete Node 8 Traversal:**\n    - Add `8` to `result`: `result = [2, 6, 14, 11, 7, 3, 12, 8]`.\n    - Return to the previous call (Node `4`).\n\n17. **Complete Node 4 Traversal:**\n    - Add `4` to `result`: `result = [2, 6, 14, 11, 7, 3, 12, 8, 4]`.\n    - Return to the previous call (Node `1`).\n\n18. **Traverse Child 5 of Node 1:**\n    - Call `traverse(5, result)`.\n    - Node `5` has children `[9, 10]`.\n\n19. **Traverse Child 9 of Node 5:**\n    - Call `traverse(9, result)`.\n    - Node `9` has children `[13]`.\n\n20. **Traverse Child 13 of Node 9:**\n    - Call `traverse(13, result)`.\n    - Node `13` has no children.\n    - Add `13` to `result`: `result = [2, 6, 14, 11, 7, 3, 12, 8, 4, 13]`.\n    - Return to the previous call (Node `9`).\n\n21. **Complete Node 9 Traversal:**\n    - Add `9` to `result`: `result = [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9]`.\n    - Return to the previous call (Node `5`).\n\n22. **Traverse Child 10 of Node 5:**\n    - Call `traverse(10, result)`.\n    - Node `10` has no children.\n    - Add `10` to `result`: `result = [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10]`.\n    - Return to the previous call (Node `5`).\n\n23. **Complete Node 5 Traversal:**\n    - Add `5` to `result`: `result = [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5]`.\n    - Return to the previous call (Node `1`).\n\n24. **Complete Node 1 Traversal:**\n    - Add `1` to `result`: `result = [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1]`.\n\n25. **Return Result:**\n    - The final output of the traversal is `[2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1]`.\n\n
['Stack', 'Tree', 'Depth-First Search', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'Kotlin', 'C#']