Maximum Depth of N-ary Tree

• If the root is null, return 0.
• Initialize a Queue and add the root node.
• Initialize depth to 0.
• While the queue is not empty:
  • Get the number of nodes at the current level, levelSize.
  • Increment depth.
  • Loop levelSize times:
    • Dequeue a node.
    • Enqueue all of its children.
• Return depth.

The algorithm works by performing a level-order traversal.

• We start with a queue containing just the root node and initialize the depth to 0.
• We then enter a loop that continues as long as there are nodes to process in the queue.
• In each iteration of the loop, we process one full level of the tree. We first record the number of nodes currently in the queue (levelSize). These are all the nodes at the current depth.
• We increment our depth counter because we are moving one level deeper.
• We then dequeue levelSize nodes, and for each node, we enqueue all of its children. This prepares the queue with all nodes for the next level.
• Once the queue is empty, it means we have visited all nodes, and the depth counter holds the maximum depth of the tree.

1/*2// Definition for a Node.3class Node {4    public int val;5    public List<Node> children;6 7    public Node() {}8 9    public Node(int _val) {10        val = _val;11    }12 13    public Node(int _val, List<Node> _children) {14        val = _val;15        children = _children;16    }17};18*/19import java.util.LinkedList;20import java.util.Queue;21import java.util.List;22 23class Solution {24    public int maxDepth(Node root) {25        if (root == null) {26            return 0;27        }28        29        Queue<Node> queue = new LinkedList<>();30        queue.offer(root);31        32        int depth = 0;33        34        while (!queue.isEmpty()) {35            int levelSize = queue.size();36            depth++;37            for (int i = 0; i < levelSize; i++) {38                Node currentNode = queue.poll();39                if (currentNode.children != null) {40                    for (Node child : currentNode.children) {41                        queue.offer(child);42                    }43                }44            }45        }46        47        return depth;48    }49}

• If the root is null, return 0 (base case).
• Initialize maxChildDepth to 0.
• For each child of the root:
  • Recursively call maxDepth(child) and update maxChildDepth with the maximum value found so far.
• Return 1 + maxChildDepth.

The core idea is to define the depth of a tree in terms of the depths of its subtrees.

• The base case for the recursion is a null node, which has a depth of 0.
• For a non-null node, we need to find the maximum depth among all its children. We initialize a variable, maxChildDepth, to 0.
• We then iterate through each child of the current node and make a recursive call to maxDepth on that child.
• We keep track of the maximum depth returned by these recursive calls in maxChildDepth.
• Finally, the depth of the tree rooted at the current node is 1 (for the node itself) plus the maxChildDepth. This value is returned.

1/*2// Definition for a Node.3class Node {4    public int val;5    public List<Node> children;6 7    public Node() {}8 9    public Node(int _val) {10        val = _val;11    }12 13    public Node(int _val, List<Node> _children) {14        val = _val;15        children = _children;16    }17};18*/19import java.util.List;20 21class Solution {22    public int maxDepth(Node root) {23        if (root == null) {24            return 0;25        }26        27        int maxChildDepth = 0;28        if (root.children != null) {29            for (Node child : root.children) {30                maxChildDepth = Math.max(maxChildDepth, maxDepth(child));31            }32        }33        34        return 1 + maxChildDepth;35    }36}