Problem of The Day: N-ary Tree Postorder Traversal

Problem Statement

Intuition

When faced with a tree traversal problem, I first thought about how postorder traversal works: I need to visit all the children of a node before visiting the node itself. This “bottom-up” approach naturally led me to think of recursion as a fitting solution.

Approach

To solve the problem, I decided to use a helper function that recursively traverses the tree. The helper function starts from the root node, recursively visits each child, and finally appends the value of the current node to the result list. By doing this recursively, I ensure that I process all children before the parent node, which aligns perfectly with the postorder traversal definition.

Complexity

• Time complexity: The time complexity of this approach is \(O(n)\), where n is the number of nodes in the tree. This is because I visit each node exactly once.
• Space complexity: The space complexity is \(O(n)\) in the worst case due to the call stack during recursion, especially in cases where the tree is highly unbalanced (e.g., a tree that is essentially a linked list).

Code

"""
# 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]:
        def helper(node, res):
            if not node:
                return
            for child in node.children:
                helper(child, res)
            res.append(node.val)
            return res
        return helper(root, [])

Editorial

Approach 1: Recursive

class Solution:
    def postorder(self, root: "Node") -> List[int]:
        result = []
        if not root:
            return result
        self._traverse_postorder(root, result)
        return result

    def _traverse_postorder(
        self, current_node: "Node", postorder_list: List[int]
    ) -> None:
        if not current_node:
            return

        # First, visit all children
        for child_node in current_node.children:
            self._traverse_postorder(child_node, postorder_list)

        # Then, add the current node's value
        postorder_list.append(current_node.val)

Approach 2: Iterative (Explicit Reversal)

class Solution:
    def postorder(self, root: "Node") -> List[int]:
        result = []

        # If the root is None, return the empty list
        if root is None:
            return result

        node_stack = [root]

        # Traverse the tree using the stack
        while node_stack:
            current_node = node_stack.pop()
            result.append(current_node.val)
            # Push all the children of the current node to the stack
            for child in current_node.children:
                node_stack.append(child)

        # Reverse the result list to get the correct postorder traversal
        result.reverse()
        return result