Leetcode Daily Question 26/08/2024 - 590. N-ary Tree Postorder Traversal

Problem Description:

Given the root of an n-ary tree, return the postorder traversal of its nodes' values. Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

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 traversal(node):
      if node:
        for child in node.children:
          traversal(child)
        result.append(node.val)
    traversal(root)
    return result

Explanation:

Traversing a n-ary tree is similar to traversing a binary tree. The only difference is instead of having at most 2 child node, an n-ary tree has n many.

To perform postorder traversal we use a recursive method as we would with a binary tree.

Recall that postorder traversal is "left, right, root".

So for each node, we would traverse to the deepest left node first and go from there. We do this by exploring every child of the node.

def traversal(node):
  if node:
    for child in node.children:
      traversal(child)
    result.append(node.val)

The time complexity is O(n) as we need to traverse every node.

The space complecity is also O(n) as we need to store all of the nodes' values.

The full solution can be found near the top of the page.