LeetCode 559 - Maximum Depth of N-ary Tree

https://leetcode.com/problems/maximum-depth-of-n-ary-tree/

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.

For example, given a 3-ary tree:

We should return its max depth, which is 3.

Note:

1. The depth of the tree is at most 1000.
2. The total number of nodes is at most 5000.

• Time complexity : we visit each node exactly once, thus the time complexity is $\mathcal{O}(N)$, where $N$ is the number of nodes.
• Space complexity : in the worst case, the tree is completely unbalanced, e.g. each node has only one child node, the recursion call would occur $N$ times (the height of the tree), therefore the storage to keep the call stack would be $\mathcal{O}(N)$. But in the best case (the tree is completely balanced), the height of the tree would be $\log(N)$. Therefore, the space complexity in this case would be $\mathcal{O}(\log(N))$. 

  public int maxDepth(Node root) {

    if (root == null) {

      return 0;

    } else if (root.children.isEmpty()) {

      return 1;  

    } else {

      List<Integer> heights = new LinkedList<>();

      for (Node item : root.children) {

        heights.add(maxDepth(item)); 

      }

      return Collections.max(heights) + 1;

    }

  }

https://leetcode.com/problems/maximum-depth-of-n-ary-tree/discuss/148544/Java-Top-down-DFS-solutions

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




We could also convert the above recursion into iteration, with the help of stack.

The idea is to visit each node with the DFS strategy, while updating the max depth at each visit.

So we start from a stack which contains the root node and the corresponding depth which is 1. Then we proceed to the iterations: pop the current node out of the stack and push the child nodes. The depth is updated at each step.

  public int maxDepth(Node root) {

    Queue<Pair<Node, Integer>> stack = new LinkedList<>();

    if (root != null) {

      stack.add(new Pair(root, 1));

    }

    int depth = 0;

    while (!stack.isEmpty()) {

      Pair<Node, Integer> current = stack.poll();

      root = current.getKey();

      int current_depth = current.getValue();

      if (root != null) {

        depth = Math.max(depth, current_depth);

        for (Node c : root.children) {

          stack.add(new Pair(c, current_depth + 1));    

        }

      }

    }

    return depth;

  }

X. BFS
https://leetcode.com/problems/maximum-depth-of-n-ary-tree/discuss/183060/Java-BFS-Iterative-Solution

public int maxDepth(Node root) {
    if(root == null) return 0;
    
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    
    int depth = 0;
    
    while(!queue.isEmpty())
    {
        int size = queue.size();
        
        for(int i = 0; i < size; i++)
        {
            Node current = queue.poll();
            for(Node child: current.children) queue.offer(child);
        }
        
        depth++;
    }
    
    return depth;
}