algoadvance

LeetCode Problem 559: “Maximum Depth of N-ary Tree”

Given an N-ary tree, find its maximum depth.

An N-ary tree is simply a tree in which a node can have at most N children. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

        1
       /|\
      3 2 4
     / \
    5   6

The maximum depth of this tree is 3.

Clarifying Questions

  1. Function Signature:
    • The function will be named maxDepth.
    • It will accept a single argument, root, which is the root node of the N-ary tree.
    • It will return an integer representing the maximum depth of the tree.
  2. Edge Cases:
    • What should the function return if the tree is empty? (Return 0).
    • Are there any constraints on the node values? (Assume all node values are valid integers).

Strategy

  1. Depth-First Search (DFS):
    • Use a recursive DFS approach to traverse the tree and calculate the maximum depth.
    • If the node is None, return 0.
    • Initialize the depth as 1 if the node has no children.
    • For each child of the current node, calculate the depth recursively and take the maximum value among them.
  2. Breadth-First Search (BFS):
    • Use an iterative BFS approach with a queue.
    • Initialize the queue with the root node and a depth of 1.
    • Traverse each level of the tree, increasing the depth by 1 for each level.

Given the recursion’s simplicity for this problem, we’ll implement the recursive DFS solution.

Time Complexity

Code

Here’s the implementation using the DFS approach:

# 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 not root:
            return 0
        elif not root.children:
            return 1
        else:
            max_depth = 0
            for child in root.children:
                max_depth = max(max_depth, self.maxDepth(child))
            return max_depth + 1

In this code:

  1. We check if root is None. If so, the depth is 0.
  2. If the root node has no children, the depth is 1.
  3. If the node has children, we recursively calculate the maximum depth of each child and use the maximum value to determine the depth of the current node.

Running the above code will correctly return the maximum depth of an N-ary tree as expected.

Try our interview co-pilot at AlgoAdvance.com