Max Depth N-ary Tree LeetCode 559 Guide

LeetCode 559 asks you to find the maximum depth of an N-ary tree. Given the root of an N-ary tree, return its maximum depth — the number of nodes along the longest path from the root node down to the farthest leaf node.

Unlike a binary tree where each node has at most a left and a right child, an N-ary tree node holds a list of children. The list can be empty (leaf node), contain one child, or contain many children. Your solution must handle all of these cases correctly.

This problem appears in interviews as a follow-up to Maximum Depth of Binary Tree (LeetCode 104). Interviewers want to see if you can abstract the pattern from two fixed pointers to an arbitrary list of children.

For a binary tree the depth formula is: depth(node) = 1 + max(depth(left), depth(right)). You take the maximum of two children. For an N-ary tree the idea is exactly the same — you just take the maximum over all children in the list instead of a fixed left and right.

N-ary depth formula: depth(node) = 1 + max(depth(child) for child in node.children). If the children list is empty the max of an empty sequence is 0, so depth returns 1 — correctly identifying a leaf. The recursive structure is identical to the binary case; only the iteration target changes.

This abstraction is powerful. Once you internalize "max over children" as the N-ary generalization of "max of two sides," tree depth problems of any branching factor become trivial variations of the same template.

The recursive DFS solution is the most concise. The base case is a null root, which returns 0. For any non-null node, recursively compute the depth of each child and return 1 plus the maximum child depth. If the children list is empty, the max is 0 and the function returns 1.

Python implementation: def maxDepth(root) — if not root: return 0; return 1 + max((maxDepth(c) for c in root.children), default=0). The default=0 in Python's max handles the empty children list gracefully without an explicit leaf check.

Java implementation: public int maxDepth(Node root) — if (root == null) return 0; int max = 0; for (Node child : root.children) max = Math.max(max, maxDepth(child)); return max + 1. Both implementations run in O(n) time and O(h) space where h is the tree height (call stack depth).

The BFS approach counts the number of levels in the tree. Enqueue the root, then process nodes level by level. Each time you finish a level, increment the depth counter. When the queue is empty all levels have been counted and the counter equals the maximum depth.

The key pattern: at the start of each level snapshot the queue size. Process exactly that many nodes, enqueuing all their children. After processing all nodes at the current level, increment depth by 1. Repeat until no nodes remain.

BFS time complexity is O(n) — every node is enqueued and dequeued exactly once. Space complexity is O(w) where w is the maximum width of the tree (the largest number of nodes at any single level). For wide, shallow trees BFS uses more memory than DFS; for narrow, deep trees DFS uses more.

Consider an N-ary tree where the root has value 1 and three children with values 3, 2, and 4. Node 3 has two children with values 5 and 6. Nodes 2, 4, 5, and 6 are all leaves.

Recursive DFS trace: maxDepth(root=1) calls maxDepth(3), maxDepth(2), maxDepth(4). maxDepth(3) calls maxDepth(5) and maxDepth(6), both return 1, so maxDepth(3) = 1 + max(1,1) = 2. maxDepth(2) = 1, maxDepth(4) = 1. Back at root: 1 + max(2,1,1) = 3.

BFS trace: Level 1 — dequeue root(1), enqueue [3,2,4]; depth=1. Level 2 — dequeue 3,2,4; enqueue [5,6]; depth=2. Level 3 — dequeue 5,6; enqueue nothing; depth=3. Queue empty, return 3. Both approaches confirm the maximum depth is 3.

Python recursive (3 meaningful lines): def maxDepth(self, root) — if not root: return 0; return 1 + max((self.maxDepth(c) for c in root.children), default=0). The default=0 keyword argument to max handles leaf nodes without an extra branch.

Python BFS with deque: from collections import deque. If not root return 0. Initialize queue = deque([root]), depth = 0. While queue: depth += 1; for _ in range(len(queue)): node = queue.popleft(); queue.extend(node.children). Return depth. Both solutions are O(n) time.

Java recursive mirrors the Python logic with a for-each loop. Java BFS uses a LinkedList as a queue and adds all children with addAll(node.children). The structure of both BFS implementations is identical — the only language difference is syntax.

Maximum Depth of Binary Tree (LeetCode 104) is the binary special case of this problem. Minimum Depth of Binary Tree (LeetCode 111) adds a twist: a node with only one child is not a leaf, so you must distinguish one-child nodes from actual leaves. Balanced Binary Tree (LeetCode 110) combines left and right depths to check if their difference exceeds one.

The depth pattern family shares the same recursive skeleton: compute child depths, combine them with some aggregation (max, min, or difference check), and add 1 for the current level. Mastering LeetCode 559 solidifies your intuition for all of these because the N-ary case forces you to think of children as a collection rather than two fixed variables.

For interview preparation, practice LeetCode 104, 111, 110, and 559 as a suite. Each adds a constraint that tests a slightly different aspect of depth reasoning. Once you can write all four from memory, depth-related tree problems in interviews become straightforward pattern recognition.