algoadvance

Given the root of an N-ary tree, return the postorder traversal of its nodes’ values.

N-ary Tree: In an N-ary tree, a node can have at most N children.

Example:

Input: root = [1,null,3,2,4,null,5,6]
Output: [5,6,3,2,4,1]

Clarifying Questions

  1. What does the input structure look like?
    • The input root is a Node object representing the root of an N-ary tree.
  2. What is the definition of the Node class? 
    class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
  3. Are there any constraints or edge cases we should be aware of?
    • The number of nodes in the tree is in the range [0, 10^4].
    • The value of each node is in the range [0, 10^4].

Strategy

The postorder traversal visits each node’s children before visiting the node itself. This can be naturally implemented using recursion, but an iterative approach is also possible using a stack.

Recursive Approach:

  1. Define a helper function postOrderTraversal that takes a node and a result list.
  2. Recursively call this helper function on each of the node’s children.
  3. Append the node’s value to the result list.

Iterative Approach with a Stack:

  1. Use a stack to simulate the recursive traversal.
  2. Push the root node and its children onto the stack.
  3. While the stack is not empty:
    • Pop a node from the stack.
    • Add the node’s value to the front of the result list.
    • Push the node’s children onto the stack.

Code

Recursive Approach:

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        def traverse(node, result):
            if node is None:
                return
            for child in node.children:
                traverse(child, result)
            result.append(node.val)
        
        result = []
        traverse(root, result)
        return result

Iterative Approach:

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        stack, result = [root], []
        while stack:
            node = stack.pop()
            result.append(node.val)
            for child in node.children:
                stack.append(child)
        return result[::-1]

Time Complexity

Both the recursive and iterative solutions have a time complexity of (O(N)), where (N) is the number of nodes in the tree. This is because each node is visited exactly once.

Space Complexity

In summary, both solutions are efficient and appropriate for the given problem constraints. The choice between the two may depend on the preferred style (recursive vs. iterative).

Try our interview co-pilot at AlgoAdvance.com