We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Depth of N-ary Tree

Number: 774

Difficulty: Easy

Paid? No

Companies: Datadog

Problem Description

Given an n-ary tree, determine its maximum depth, which is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Key Insights

  • Use recursion (DFS) to traverse each node and compute the depth.
  • At each node, evaluate the maximum depth among its children.
  • A breadth-first search (BFS) can also be used by traversing level by level.
  • Account for an empty tree, where the depth is 0.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since every node is visited once. Space Complexity: O(h) in the recursive solution, where h is the height of the tree, due to the recursion call stack. In the worst-case (a skewed tree), h can be equal to n.

Solution

We solve the problem using a recursive depth-first search (DFS) approach. For each node, we recursively compute the maximum depth of its children and add one for the current node. If a node is null or has no children, the depth is 1 (or 0 if the tree is empty). The key step is to traverse through all children of each node and keep track of the maximum depth among them. This approach efficiently explores all paths in the tree and returns the longest.

Code Solutions

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

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # If the root is None, then the tree is empty, so depth is 0
        if root is None:
            return 0
        # If there are no children, the tree has only one node
        if not root.children:
            return 1
        # Recursively compute the maximum depth among all children
        max_child_depth = 0
        for child in root.children:
            child_depth = self.maxDepth(child)
            # Update max_child_depth if a deeper child is found
            max_child_depth = max(max_child_depth, child_depth)
        # Add 1 for the current node and return the total depth
        return 1 + max_child_depth

# Example usage:
# root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)])
# print(Solution().maxDepth(root))
← Back to All Questions