Maximum Depth of N-ary Tree

easy tree dfs bfs

Problem

Given an n-ary tree, return its maximum depth: the number of nodes along the longest path from the root down to the farthest leaf.

Inputroot = [1, [3, [5, 6], 2, 4]]

Output3

Depth(root) = 1 + max(depth of each child).

tree (nested JS list, e.g. [1,[2,3,[4]]])

def max_depth(root):
    if not root: return 0
    if not root.children: return 1
    return 1 + max(max_depth(c) for c in root.children)

function maxDepth(root) {
  if (!root) return 0;
  if (!root.children || !root.children.length) return 1;
  return 1 + Math.max(...root.children.map(maxDepth));
}

class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int best = 0;
        for (Node c : root.children) best = Math.max(best, maxDepth(c));
        return 1 + best;
    }
}

int maxDepth(Node* root) {
    if (!root) return 0;
    int best = 0;
    for (auto c : root->children) best = max(best, maxDepth(c));
    return 1 + best;
}

Explanation

An n-ary tree is like a binary tree except a node can have any number of children instead of just two. The depth idea stays exactly the same: a node's depth is 1 + the deepest of its children.

So instead of comparing only a left and right subtree, we take the max depth across all children in the root.children list and add one.

There are two simple base cases. An empty tree (not root) has depth 0, and a node with no children is a leaf with depth 1.

The line 1 + max(max_depth(c) for c in root.children) recurses into every child, finds the tallest one, and adds the current level.

Example: [1, [3, [5, 6], 2, 4]]. Node 3 has a child 5 that itself holds 6, so the chain 1 → 3 → 5 (or 1 → 3 → 6) is length 3, which is the answer.

Time: O(n) Space: O(h) recursion