Maximum Depth of N-ary Tree

LeetCode 774 | Difficulty: Easy

Easy

Problem Description

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 (See examples).

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 5

Constraints:

- The total number of nodes is in the range `[0, 10^4]`.

- The depth of the n-ary tree is less than or equal to `1000`.

Topics: Tree, Depth-First Search, Breadth-First Search

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

Tree BFS (Level-Order)

Use a queue to process the tree level by level. At each level, process all nodes in the queue, then add their children. Track the level size to know when one level ends and the next begins.

When to use

Level-order traversal, level-based aggregation, right/left side view.

---

Solutions

Solution 1: C# (Best: 560 ms)

Metric	Value
Runtime	560 ms
Memory	33.8 MB
Date	2020-01-26

Solution

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}
*/
public class Solution {
    public int MaxDepth(Node root) {
        if(root == null) return 0;
        if(root.children == null || root.children.Count == 0) return 1;
        List<int> heights = new List<int>();
        foreach (var child in root.children)
        {           
            heights.Add(MaxDepth(child));
        }
        return 1+ heights.Max();
    }
}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.