N-ary Tree Postorder Traversal - Solution
Solutions and explanations
"""
# Definition for a Node.
class Node:
def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
self.val = val
self.children = children
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
result = []
def dfs(node):
if node:
for child in node.children:
dfs(child)
result.append(node.val)
dfs(root)
return result
Complexity Analysis
Here, n is the number of nodes in the tree, and h is the height of the tree.
- Time Complexity:
O(n)- Each node is visited during traversal.
- Space Complexity:
O(n)- Output space is
O(n)- for storing the result list. - Recursion stack space is
O(h)- and in the worst case,hcan be up toO(n)(for example: in a skewed tree).
- Output space is
"""
# Definition for a Node.
class Node:
def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
self.val = val
self.children = children
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
result = []
stack = [root]
while stack:
node = stack.pop()
if node:
result.append(node.val)
if node.children:
# Push children left-to-right so rightmost child stays on top and pops first
stack.extend(node.children)
return result[::-1] # Reverse to convert [Root -> Rightmost ... Leftmost] into [Leftmost ... Rightmost -> Root] (i.e. postorder)
Complexity Analysis
Here, n is the number of nodes in the tree.
- Time Complexity:
O(n)- Each node is visited during traversal.
- Space Complexity:
O(n)- Output space:
O(n)- for storing the result list. - Stack space:
O(n)- In the iterative version, the stack can grow up toO(n)in the worst case (for example: in a wide or skewed tree), because it may temporarily hold many nodes at once, especially when a node has multiple children (unlike the recursive version, where the call stack is limited to the tree height).
- Output space: