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.
Input: root = [1,null,3,2,4,null,5,6] Output: 3
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
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.