Leetcode – N-ary Tree Preorder Traversal Solution in Python

Spread the love

Navigating through trees is an essential skill in computer science, and N-ary trees introduce an additional layer of complexity. In this comprehensive guide, we’ll dissect the N-ary Tree Preorder Traversal problem found on Leetcode, understand the intricacies of traversing N-ary trees, and learn how to solve this problem efficiently in Python.

Problem Statement

Leetcode problem #589 is titled “N-ary Tree Preorder Traversal” and the problem statement is as follows:

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

N-ary Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.

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

Understanding N-ary Trees

Before we delve into solving the problem, it’s crucial to understand what N-ary trees are. 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.

Definition of N-ary Tree Node

Let’s define the structure of an N-ary Tree node. This will be used to construct the tree:

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 of the most intuitive ways to perform a preorder traversal is by using recursion. The essence of preorder traversal is to visit the root node first, followed by its children from left to right.

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

Explanation:

  1. If the root is None, we return an empty list.
  2. Add the value of the root node to the result list.
  3. Recursively call the preorder function for each child and extend the result list with the values returned.

Time Complexity:

The time complexity of this approach is O(n), where n is the number of nodes in the tree. 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 also perform preorder traversal iteratively using a stack. This approach emulates the function call stack used in the recursive approach.

class Solution:
    def preorder(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[::-1])
            
        return result

Explanation:

  1. If the root is None, we return an empty list.
  2. Use a stack to emulate the call stack used in the recursive approach. 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 add its children to the stack in reverse order (rightmost child first).
  4. Return the result list.

Time Complexity:

The time complexity of this approach is O(n), as each node is visited once. The space complexity is also O(n) due to the stack used for iteration.

Conclusion

N-ary trees are a generalization of binary trees, and understanding how to traverse them efficiently is an essential skill. We explored two approaches to solve the N-ary Tree Preorder Traversal problem on LeetCode using Python – the recursive approach and the iterative approach using a stack. Both approaches have linear time complexity. The choice between them can be based on personal preference, although the iterative approach may be more efficient in terms of space in certain scenarios.

Leave a Reply