# LeetCode 590: N-ary Tree Postorder Traversal ## Problem Restatement We are given the `root` of an N-ary tree. An N-ary tree is a tree where each node may have any number of children. We need to return the postorder traversal of the tree's node values. In postorder traversal, we visit: 1. All children from left to right. 2. The current node after its children. The input may be empty. If the tree has no nodes, return an empty list. The number of nodes is in the range `[0, 10^4]`, node values are between `0` and `10^4`, and the tree height is at most `1000`. The follow-up asks for an iterative solution. ([leetcode.com](https://leetcode.com/problems/n-ary-tree-postorder-traversal/), [github.com](https://github.com/doocs/leetcode/blob/main/solution/0500-0599/0590.N-ary%20Tree%20Postorder%20Traversal/README_EN.md)) ## Input and Output | Item | Meaning | |---|---| | `root` | Root node of an N-ary tree | | Output | List of node values in postorder | | Empty tree | Return `[]` | The node structure is usually given as: ```python class Node: def __init__(self, val=None, children=None): self.val = val self.children = children ``` Example function shape: ```python def postorder(root: "Node") -> list[int]: ... ``` ## Examples Example 1: ```text root = [1,null,3,2,4,null,5,6] ``` This represents: ```text 1 / | \ 3 2 4 / \ 5 6 ``` Output: ```python [5, 6, 3, 2, 4, 1] ``` We first visit the children of `3`, then `3`, then `2`, then `4`, and finally the root `1`. Example 2: ```python root = [] ``` Output: ```python [] ``` An empty tree has no nodes to visit. ## First Thought: Recursive DFS Postorder traversal is naturally recursive. For each node: 1. Recursively visit every child from left to right. 2. Add the current node's value to the answer. This is the opposite order from preorder. In preorder, we append the node before its children. In postorder, we append the node after its children. ## Key Insight A postorder traversal processes descendants before ancestors. For an N-ary tree, the rule is: ```text visit child subtree 1 visit child subtree 2 ... visit child subtree k visit node ``` So the DFS function should delay appending `node.val` until after all recursive child calls finish. ## Algorithm 1. Create an empty result list. 2. Define a DFS function. 3. If the current node is `None`, stop. 4. For each child in `node.children`, recursively call DFS. 5. Append the current node's value. 6. Return the result list. ## Correctness The algorithm visits every child subtree of a node before appending the node's own value. This matches the definition of postorder traversal. For each child, the same rule is applied recursively. Therefore, all descendants of that child are also visited before the child itself. Since children are processed in the order they appear in `node.children`, the traversal respects the required left-to-right child order. The base case handles an empty node by adding nothing, which is correct for an empty subtree. Therefore, the result list contains exactly the postorder traversal of the N-ary tree. ## Complexity Let: ```text n = number of nodes in the tree h = height of the tree ``` | Metric | Value | Why | |---|---|---| | Time | `O(n)` | Each node is visited once | | Space | `O(h)` | The recursion stack stores one root-to-leaf path | The output list uses `O(n)` space. ## Implementation ```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]: result = [] def dfs(node: "Node") -> None: if node is None: return for child in node.children: dfs(child) result.append(node.val) dfs(root) return result ``` ## Code Explanation The result list stores the traversal: ```python result = [] ``` The helper function traverses one subtree: ```python def dfs(node): ``` The empty tree case is: ```python if node is None: return ``` For postorder, we visit all children first: ```python for child in node.children: dfs(child) ``` Only after all children are processed do we append the current node: ```python result.append(node.val) ``` Finally, we start traversal from the root: ```python dfs(root) ``` ## Iterative Implementation The follow-up asks for an iterative solution. One clean approach is to use a stack and build a reversed root-first traversal. If we process nodes in this order: ```text node, children from left to right ``` and then reverse the final result, we get postorder. To make this work with a stack, we push children in normal order. Since the stack is last-in, first-out, the rightmost child is processed first, and reversing the final list restores left-to-right postorder. ```python class Solution: def postorder(self, root: "Node") -> list[int]: if root is None: return [] result = [] stack = [root] while stack: node = stack.pop() result.append(node.val) for child in node.children: stack.append(child) return result[::-1] ``` For the tree: ```text 1 / | \ 3 2 4 / \ 5 6 ``` the stack process creates: ```python [1, 4, 2, 3, 6, 5] ``` Reversing it gives: ```python [5, 6, 3, 2, 4, 1] ``` which is the required postorder traversal. ## Testing ```python class Node: def __init__(self, val=None, children=None): self.val = val self.children = children or [] def run_tests(): s = Solution() root = Node(1, [ Node(3, [Node(5), Node(6)]), Node(2), Node(4), ]) assert s.postorder(root) == [5, 6, 3, 2, 4, 1] assert s.postorder(None) == [] single = Node(1) assert s.postorder(single) == [1] chain = Node(1, [Node(2, [Node(3)])]) assert s.postorder(chain) == [3, 2, 1] wide = Node(1, [Node(2), Node(3), Node(4)]) assert s.postorder(wide) == [2, 3, 4, 1] print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | Sample tree | Checks standard postorder behavior | | Empty tree | Returns an empty list | | Single node | Returns only the root | | Deep chain | Children are returned before ancestors | | Wide tree | Children are visited left to right |