Leetcode – Maximum Depth of N-ary Tree Solution in Python

Spread the love

Introduction

Trees are one of the most vital data structures in computer science, and have extensive applications in various fields. While binary trees are widely discussed and used, N-ary trees are equally important and can represent more complex hierarchical relationships. One of the common problems related to trees is finding their depth or height. In this comprehensive article, we will focus on the Maximum Depth of N-ary Tree problem available on Leetcode, understand the critical concepts behind it, and craft a Python solution.

The problem is described as follows:

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

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

For example:

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

N-ary Trees

Unlike binary trees, where each node has at most two children, in an N-ary tree, each node can have multiple children.

Recursive Approach: Depth-First Search (DFS)

One of the most natural approaches to solve this problem is to use recursion. The maximum depth of an N-ary tree is 1 (the root itself) plus the maximum depth of its subtrees. We can perform a depth-first traversal and keep track of the depth as we recurse through the tree.

Here is the Python code for this approach:

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # Base case: if the tree is empty, depth is 0
        if not root:
            return 0
        
        # Recursive case: 1 + max depth of the subtrees
        max_subtree_depth = 0
        for child in root.children or []:
            max_subtree_depth = max(max_subtree_depth, self.maxDepth(child))
        
        return 1 + max_subtree_depth

This recursive approach has a time complexity of O(n), where n is the number of nodes in the tree, as we visit each node once. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack.

Iterative Approach: Breadth-First Search (BFS)

An alternative approach is to use an iterative breadth-first search (BFS). We can traverse the tree level by level and keep track of the depth.

Here’s the Python code for this approach:

from collections import deque

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # Base case: if the tree is empty, depth is 0
        if not root:
            return 0
        
        # Initialize the queue for BFS
        queue = deque([(root, 1)])
        
        # Initialize the maximum depth
        max_depth = 0
        
        # Perform BFS
        while queue:
            # Dequeue a node and its depth
            node, depth = queue.popleft()
            
            # Update the maximum depth
            max_depth = max(max_depth, depth)
            
            # Enqueue the children along with their depth
            for child in node.children or []:
                queue.append((child, depth + 1))
        
        return max_depth

This iterative approach also has a time complexity of O(n) and a space complexity of O(w), where w is the maximum width of the tree (i.e., the maximum number of nodes in a single level).

Testing the Solutions

Let’s test the solutions with some examples:

# Define the N-ary tree from the example
root = Node(1)
child1 = Node(3, children=[Node(5), Node(6)])
child2 = Node(2)
child3 = Node(4)
root.children = [child1, child2, child3]

# Create the Solution instance
solution = Solution()

# Test Case
print(solution.maxDepth(root))  # Output should be 3

Conclusion

In this exhaustive article, we explored the Maximum Depth of N-ary Tree problem on Leetcode. We uncovered the concepts behind N-ary trees and their depth, and we delved into two different approaches to solve the problem: Recursive Depth-First Search and Iterative Breadth-First Search. Understanding the depths of trees is essential as it serves as a foundation for solving more intricate tree-based problems.

Leave a Reply