559. Maximum Depth of N-ary Tree

EasyTreeDepth-First SearchBreadth-First Search

Problem Description

The given problem focuses on determining the maximum depth of a n-ary tree. In a tree data structure, the depth represents the length of the path from the root node to the farthest leaf node. For a n-ary tree, which means that each node can have an arbitrary number of children, we define the tree's maximum depth as the largest number of steps it takes to travel from the root node to a leaf node. It should be noted that the root node itself is counted as a step. In this context, a leaf node is a node with no children. The tree is provided in a serialized form that reflects its level-order traversal where groups of children nodes are separated by a null value.

Flowchart Walkthrough

To determine the appropriate algorithm approach for LeetCode 559: Maximum Depth of N-ary Tree, let's consult the Flowchart. I'll guide you step-by-step through the decision process:

Is it a graph?
- Yes: An N-ary tree can be represented as a graph where each node represents a tree node, and edges represent parent-child relationships.
Is it a tree?
- Yes: An N-ary tree is indeed a tree as it's a hierarchical data structure.
DFS (Depth-First Search)
- At this decision point in the flowchart, having identified that the structure is a tree, we proceed directly to considering Depth-First Search pattern for traversing or processing the tree. In the specific problem of finding the maximum depth, DFS is a natural fit because it explores as deep as possible along each branch before backtracking, which is ideal for depth determination.

Conclusion: Following the flowchart's logic and the nature of the problem suggests that Depth-First Search is the most suitable algorithm for finding the maximum depth of an N-ary tree.

Intuition

The solution relies on a depth-first search (DFS) approach, where we recursively explore each subtree rooted at each child of the current node. The base case for the recursive function is when it encounters a None value, which indicates an empty node or the end of a branch, and therefore it should return 0 as there are no further nodes down that path.

When the recursive function is called on a non-empty node, it computes the maximum depth of all subtrees rooted at each of its children. This is done by calling the recursive function for each child node and collecting these depths into a list. We then obtain the maximum depth from these subtrees and add 1 to it to account for the current node. The +1 represents that the path from the current node to the deepest leaf in each subtree is one step longer because of the current node.

If a node does not have any children, the max function would return a default value of 0. When we have the maximum depths of all children (if any), we select the maximum value among them, add 1 to represent the current node, and return this number. This recursive process continues until the root of the tree is reached, at which point we obtain the maximum depth of the entire n-ary tree. The recursive nature of this approach effectively navigates through all possible paths and finds the length of the longest one, thus solving the problem.

Learn more about Tree, Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation begins with checking if the root node is None. This check ensures that if the tree is empty (hence, there is no tree whatsoever), the function returns 0. After bypassing the base case, the solution uses a depth-first search (DFS) strategy to find the maximum depth.

In the context of a n-ary tree where nodes can have multiple children, each child node can potentially branch out to a tree that is a subtree. For each child node, we are interested in finding the maximum depth from that child down to its farthest leaf node.

We use a list comprehension to apply the maxDepth function recursively on each of the child nodes of the root:

[self.maxDepth(child) for child in root.children]

This recursively calculates the depth for each subtree rooted at child. As we are interested in the maximum depth, we then use the max function to find the maximum value in this list. Since it's possible for a node to have no children, leading to an empty list, we specify a default value (which is 0) to the max function. This default value is returned when the max function is called on an empty list:

max([self.maxDepth(child) for child in root.children], default=0)

It should be noted that if a node does have children, each recursive maxDepth call will return some integer greater than or equal to 1, since each node itself is counted as one step.

After finding the maximum depth among all children, we need to include the current node in the calculation, so we add 1 to this maximum value:

return 1 + max([self.maxDepth(child) for child in root.children], default=0)

This addition accounts for the current node as one more step on the path from the node to the deepest leaf. The recursive nature of this function ensures that we explore each node and its subsequent children to exhaustively determine the maximum depth of the n-ary tree.

In summary, the algorithm employs a recursive depth-first search strategy, efficiently calculates the depths of all subtrees of the n-ary tree, and elegantly combines those values to determine the overall maximum depth. This approach neatly uses Python's list comprehension, recursive function calls, and the max function with the default parameter to handle the specifics of a n-ary tree structure.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's visualize the solution approach using a simple n-ary tree. Consider the following n-ary tree:

Here's how the solution approach works on this tree:

Start with the root node (1). Since it is not None, proceed to its children.
Apply the maxDepth function to the children of 1, which are nodes 2 and 3.
- For node 2, it has children 4 and 5. The maxDepth will be called on each of them.
  - When maxDepth is called on 4, which is a leaf node, it will return 1.
  - Similarly, calling maxDepth on 5 will also return 1.
  - The maximum depth of the children of node 2 will be max([1, 1], default=0), which is 1.
  - Since node 2 is one step itself, add 1 to the maximum depth of its children, giving us a total of 1 + 1 = 2.
- For node 3, apply the same logic. It has children 6 and 7, which are leaf nodes.
  - The maxDepth function will return 1 for both 6 and 7.
  - The maximum depth of the children of node 3 will be max([1, 1], default=0), which is 1.
  - Including node 3 itself, the total depth is 1 + 1 = 2.
Now, consider the depths calculated for nodes 2 and 3. Both are 2.
For the root node, the maximum depth will be max([2, 2], default=0), which is 2.
The final step is to include the root node itself in the depth count, resulting in 1 + 2 = 3.

Therefore, the maximum depth of the tree is 3. This walk-through exemplifies how the recursive depth-first search systematically computes the depth of each subtree before combining the results to find the maximum depth of the entire tree.

Solution Implementation

1class Node:
2    """
3    A class representing a node in an n-ary tree.
4    """
5
6    def __init__(self, value=None, children=None):
7        """
8        Initialize a Node with a value and children.
9
10        Params:
11        value - The value of the node (an integer or None by default)
12        children - A list of child nodes (an empty list by default if None)
13        """
14        self.value = value
15        self.children = children if children is not None else []
16
17
18class Solution:
19    def maxDepth(self, root: 'Node') -> int:
20        """
21        Calculate the maximum depth of an n-ary tree.
22      
23        Params:
24        root - The root node of the n-ary tree.
25
26        Returns:
27        An integer representing the maximum depth of the tree.
28        """
29        # If the root node is None, the depth is 0
30        if root is None:
31            return 0
32      
33        # If the root node has no children, the maximum depth is 1
34        if not root.children:
35            return 1
36
37        # Calculate the depth of each subtree and find the maximum.
38        # For each child node, calculate the max depth recursively
39        # Add 1 to account for the current node's level
40        max_depth = 0
41        for child in root.children:
42            child_depth = self.maxDepth(child)
43            max_depth = max(max_depth, child_depth)
44      
45        # Return the maximum depth found among all children, plus 1 for the root
46        return 1 + max_depth
47

1import java.util.List;
2
3// Class definition for a Node in an N-ary tree
4class Node {
5    public int val;                      // Node's value
6    public List<Node> children;          // List of Node's children
7
8    public Node() {}
9
10    // Constructor with node's value
11    public Node(int val) {
12        this.val = val;
13    }
14
15    // Constructs node with value and list of children
16    public Node(int val, List<Node> children) {
17        this.val = val;
18        this.children = children;
19    }
20}
21
22class Solution {
23    // Method to calculate the maximum depth of an N-ary tree
24    public int maxDepth(Node root) {
25        // An empty tree has a depth of 0.
26        if (root == null) {
27            return 0;
28        }
29
30        int maxDepth = 0; // Initialize max depth as 0
31
32        // Loop through each child of root node
33        for (Node child : root.children) {
34            // Calculate the depth for each child and compare it with current max depth
35            // 1 is added to include the current node's depth
36            maxDepth = Math.max(maxDepth, 1 + maxDepth(child));
37        }
38
39        // Since we're already at root, we add 1 to account for the root's depth
40        return maxDepth + 1;
41    }
42}
43

1#include <algorithm> // Include algorithm library for max function
2#include <vector>    // Include vector library for the vector type
3
4// Definition for a Node.
5class Node {
6public:
7    int val;                     // Value of the node
8    std::vector<Node*> children; // Vector of pointers to child nodes
9
10    Node() {}
11
12    Node(int _val) {
13        val = _val;
14    }
15
16    Node(int _val, std::vector<Node*> _children) {
17        val = _val;
18        children = _children;
19    }
20};
21
22class Solution {
23public:
24    // Function to calculate the maximum depth of an n-ary tree
25    int maxDepth(Node* root) {
26        // If the root is null, the depth is 0
27        if (!root) return 0;
28
29        int max_depth = 1; // Initialize max_depth to 1 to account for the root level
30
31        // Iterate through each child of the root node
32        for (auto& child : root->children) {
33            // Recursive call to maxDepth for each child, adding 1 to the result,
34            // then update max_depth with the maximum of it and the current max_depth
35            max_depth = std::max(max_depth, 1 + maxDepth(child));
36        }
37
38        // Return the maximum depth of the tree
39        return max_depth;
40    }
41};
42

1// Definition for a Node.
2class Node {
3    val: number;                     // Value of the node
4    children: Node[];                // Array of child nodes
5
6    constructor(val: number, children: Node[] = []) {
7        this.val = val;
8        this.children = children;
9    }
10}
11
12// Function to calculate the maximum depth of an n-ary tree
13function maxDepth(root: Node | null): number {
14    // If the root is null, the depth is 0
15    if (!root) return 0;
16
17    let maxDepthValue = 1; // Initialize maxDepthValue to 1 to account for the root level
18
19    // Iterate through each child of the root node
20    root.children.forEach(child => {
21        // Recursive call to maxDepth for each child, adding 1 to the result,
22        // then update maxDepthValue with the maximum of it and the current maxDepthValue
23        maxDepthValue = Math.max(maxDepthValue, 1 + maxDepth(child));
24    });
25
26    // Return the maximum depth of the tree
27    return maxDepthValue;
28}
29

Time and Space Complexity

The provided code defines a function to determine the maximum depth (height) of an N-ary tree using recursion. Here's the analysis:

Time Complexity

The time complexity of the function is O(N), where N is the total number of nodes in the N-ary tree. This is because the function must visit every node exactly once to determine the depth. The recursive calls are made for each child of every node. Since each node is processed once and only once, the time complexity is linear with respect to the number of nodes.

Space Complexity

The space complexity of the function is also O(N) in the worst-case scenario. This happens when the tree is highly unbalanced, for example, when the tree degenerates into a linked list (each node has only one child). In such a case, there will be N recursive calls on the stack at the same time, where N is the depth of the tree, which is also the number of nodes in this case.

In a balanced tree, the space complexity would be O(log N) due to the height of the tree dictating the number of stack frames. However, since it is not mentioned that the tree is balanced, the worst-case space complexity is considered which is O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know