Maximum Depth of N-ary Tree

Problem

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.

Constraints

• The total number of nodes is in the range [0, 104].
• The depth of the n-ary tree is less than or equal to 1000.

Solution

The problem Maximum Depth of N-ary Tree can be solved using a depth-first search to count the length of all paths and choosing the longest one.

Implementation

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

    Node() {}

    Node(int _val) {
        val = _val;
    }

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

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

        int ret = 1;
        for (Node *node : root->children)
            ret = max(ret, maxDepth(node) + 1);

        return ret;
    }
};