algoadvance

Leetcode 559. Maximum Depth of N

Problem Statement

You are given an N-ary tree (a tree in which nodes can have an arbitrary number of children), and you need to determine the maximum depth of the tree. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

You can assume that:

• The tree is rooted and non-empty.
• Each node has an integer value and a list of children.

Clarifying Questions

1. Input Format: How is the N-ary tree represented in the input?
   • Each node is represented by a Node class, which contains an integer value and a list of child nodes.
2. Edge Cases:
   • What should be returned if the tree has only one node?
     • Return 1.
3. Constraints:
   • Depth of tree will be in a reasonable range that won’t cause stack overflow during recursion.

Strategy

To determine the maximum depth of an N-ary tree, we can use a Depth-First Search (DFS) approach. Here are the general steps:

1. Base Case: If the node is nullptr, the depth is 0.
2. Recursive Case:
   • Initialize the maximum depth at the current node to be 1.
   • For each child of the current node, recursively calculate the depth and update the maximum depth.
   • Return the maximum depth found.

The DFS approach ensures that all paths from the root to the leaf are traversed, and the longest path is identified.

Code

Here is the C++ code for calculating the maximum depth of an N-ary tree:

#include <vector>
#include <algorithm>

// Definition for a Node.
class Node {
public:
    int val;
    std::vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, std::vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == nullptr) return 0;

        int max_depth = 1;
        for (Node* child : root->children) {
            max_depth = std::max(max_depth, 1 + maxDepth(child));
        }

        return max_depth;
    }
};

Time Complexity

• Time Complexity: (O(n)), where (n) is the number of nodes in the tree. Each node is visited exactly once.
• Space Complexity: (O(h)), where (h) is the height of the tree. This is the space used by the call stack during recursion. In the worst case, the height of the tree could be (n) (in the case of a skewed tree), leading to a space complexity of (O(n)).

By structuring our solution this way, we ensure a clear and efficient traversal of the tree to find the maximum depth.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?