Maximum Depth of N-ary Tree

The maximum depth (also referred to as height) of a tree is defined as the length of the longest path from the root node down to the farthest leaf node. This path is measured by the number of nodes along this path. For instance, if the root is at Level 0, the maximum depth is the last level number plus one.

For an N-ary tree, where a node can have 'n' children instead of just two (left and right) as in a binary tree, the concept of maximum depth remains similar to that of a binary tree.

The approach to finding the maximum depth of an N-ary tree is primarily through a Depth-First Search (DFS) recursive method.

Approach for N-ary Tree (DFS)

Concept and Logic: The core idea is to recursively calculate the maximum depth of each of the children's subtrees and then take the maximum among those depths, adding 1 for the current node itself. This is a natural extension of the binary tree approach where you take 1 + Math.max(leftHeight, rightHeight). For an N-ary tree, instead of just two children, you iterate through all available children.

Step-by-step Logic:

1. Base Case: If the current root node is null, its depth is 0. This serves as the stopping condition for the recursion.

2. Initialise Max Depth for Children: For the current node, initialise a variable, say maxDepth, to 0. This variable will keep track of the maximum depth found among all its children's subtrees.

3. Iterate Through Children: Loop through each child of the current root node.

   • For each child, recursively call the maxDepth function to find its subtree's depth (currentChildDepth).

   • Update Max Depth: Compare currentChildDepth with the maxDepth found so far for the current node's children and update maxDepth if currentChildDepth is greater. This ensures you track the longest path among all children.

4. Return Value: Once all children have been processed, the maximum depth for the current root node is 1 + maxDepth (where 1 accounts for the current node itself). Return this value to the parent call.

Code Snippet Explanation (Conceptual):

// Assuming a Node class for N-ary tree has a list of children
// class Node {
//     public int val;
//     public List<Node> children;
// }

public int maxDepth(Node root) {
    if (root == null) { // Base case: If node is null, depth is 0
        return 0;
    }

    int maxDepthFoundAmongChildren = 0; // Initialize max depth for children's subtrees

    // Iterate through all children of the current node
    for (Node child : root.children) { // root.children is a list of child nodes
        // Recursively find the depth of the current child's subtree
        int currentChildDepth = maxDepth(child);

        // Update maxDepthFoundAmongChildren if currentChildDepth is greater
        if (currentChildDepth > maxDepthFoundAmongChildren) {
            maxDepthFoundAmongChildren = currentChildDepth;
        }
        // Alternatively, using Math.max:
        // maxDepthFoundAmongChildren = Math.max(maxDepthFoundAmongChildren, currentChildDepth);
    }

    // The depth for the current node is 1 (for the node itself)
    // plus the maximum depth found among its children's subtrees.
    return 1 + maxDepthFoundAmongChildren;
}

The source illustrates this logic by dry-running an example where a node calculates 1 + Max(depth of its children). If a child is null, it returns 0 depth. For instance, if a node has children whose depths are 2, 1, and 1, the maximum depth for the current node would be 1 + 2 = 3.

Time and Space Complexity

• Time Complexity: O(N), where N is the total number of nodes in the N-ary tree. Each node is visited and processed exactly once during the traversal.

• Space Complexity: O(H), where H is the height of the tree. This space is used by the recursion stack to keep track of the function calls. In the worst-case scenario, such as a skewed tree where each node has only one child, H can be equal to N, leading to O(N) space. For a balanced tree, H would be log N. The recursion stack stores information about the nodes along the current path from the root to the deepest node being processed.