Leetcode – N-ary Tree Postorder Traversal Solution in Python

Spread the love

Traversing trees is an essential concept in computer science. In this article, we are going to embark on a thorough exploration of the N-ary Tree Postorder Traversal problem (#590) on Leetcode. We will discuss the nuances of postorder traversal in N-ary trees, understand different approaches to solving this problem, and demonstrate how to implement these solutions in Python.

Problem Statement

The N-ary Tree Postorder Traversal problem statement on Leetcode is as follows:

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

N-ary Tree is defined as a tree where each node has at most N children and is represented in level order where each group of children is separated by the null value.

Example:

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

Understanding N-ary Trees

Unlike binary trees, where each node has at most two children (left and right), in N-ary trees, each node can have up to N children. This introduces an additional layer of complexity.

Definition of N-ary Tree Node

Let’s first define the structure of an N-ary Tree node:

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

Approaches to Solve the Problem

1. Recursive Approach

One way to perform postorder traversal is by using recursion. In postorder traversal, we visit all the children nodes first, from left to right, and then the root node.

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

Explanation:

  1. If the root is None, we return an empty list.
  2. For each child node, we recursively call the postorder function and extend the result list with the values returned.
  3. Finally, we append the value of the current root node to the result list.

Time Complexity:

The time complexity of the recursive approach is O(n), where n is the number of nodes in the tree, as each node is visited once. The space complexity is also O(n) due to the recursive call stack.

2. Iterative Approach using Stack

We can emulate the recursive approach by using an iterative approach with a stack. We have to be cautious of the order of nodes since it’s postorder traversal.

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        
        stack = [root]
        result = []
        
        while stack:
            current = stack.pop()
            result.append(current.val)
            stack.extend(current.children)
            
        return result[::-1]

Explanation:

  1. If the root is None, we return an empty list.
  2. We use a stack to keep track of nodes. Initialize it with the root node.
  3. While the stack is not empty, pop a node from the stack, add its value to the result list, and extend the stack with its children (in their natural order).
  4. Since we accumulated the result in a reversed manner (root first), we reverse the result list before returning it.

Time Complexity:

The time complexity of this approach is O(n) as well, with space complexity also being O(n) due to the stack.

Conclusion

In this article, we’ve delved deep into the N-ary Tree Postorder Traversal problem on LeetCode and explored two fundamental approaches to solving it using Python – the recursive approach and the iterative approach with a stack. Both approaches have their own merits and can be used based on the specific requirements of the problem at hand.

Leave a Reply