Largest Distance between nodes of a Tree

Find largest distance
Given an arbitrary unweighted rooted tree which consists of N (2 <= N <= 40000) nodes. The goal of the problem is to find largest distance between two nodes in a tree. Distance between two nodes is a number of edges on a path between the nodes (there will be a unique path between any pair of nodes since it is a tree). The nodes will be numbered 0 through N - 1.

The tree is given as an array P, there is an edge between nodes P[i] and i (0 <= i < N). Exactly one of the i’s will have P[i] equal to -1, it will be root node.

Example:
If given P is [-1, 0, 0, 0, 3], then node 0 is the root and the whole tree looks like this:
 
          0
       /  |  \
      1   2   3
               \
                4  

One of the longest path is 1 -> 0 -> 3 -> 4 and its length is 3, thus the answer is 3. Note that there are other paths with maximal distance. 
Solution:


public class Solution {
    public int solve(ArrayList<Integer> A) {
        int n = A.size();
        Map<Integer, List<Integer>> edges = new HashMap<>();
        int[] inDegrees = new int[n];
        for (int i = 0; i < n; i ++) {
            int parent = A.get(i);
            int child = i;
            List<Integer> children = edges.getOrDefault(parent, new ArrayList<>());
            children.add(child);
            edges.put(parent, children);
            
            List<Integer> children2 = edges.getOrDefault(child, new ArrayList<>());
            children2.add(parent);
            edges.put(child, children2);
            
            if (parent != -1) {
                inDegrees[parent] ++;
            }
        }
        // System.out.println(Arrays.toString(inDegrees));
        int[] max = new int[]{0};
        for (int i = 0; i < n; i ++) {
            if (inDegrees[i] == 0) {
                boolean[] visited = new boolean[n];
                dfs(0, edges, visited, 0, max);
            }
        }
        return max[0];
    }
    
    private void dfs(int i, Map<Integer, List<Integer>> edges, boolean[] visited, int pathLen, int[] max) {
        if (i == -1 || visited[i]) return;
        max[0] = Math.max(max[0], pathLen);
        visited[i] = true;
        if (edges.containsKey(i)) {
            for (int next : edges.get(i)) {
                dfs(next, edges, visited, pathLen + 1, max);
            }
        }
    }
}

Solution2:


public class Solution {
    private int maxDist = 0;
    
    public class Node {
        int val;
        int height;
        ArrayList<Node> children;
        
        public Node(int val) {
            this.val = val;
            this.height = 0;
            children = new ArrayList<>();
        }
    }
    
    private Node constructGraph(Node[] nodes, ArrayList<Integer> A) {
        Node root = null;
        for (int i = 0; i < A.size(); i++) {
            if (nodes[i] == null) {
                nodes[i] = new Node(i);
            }
            int parent = A.get(i);
            if (parent == -1) {
                root = nodes[i];
            }
            else {
                if (nodes[parent] == null) nodes[parent] = new Node(parent);
                nodes[parent].children.add(nodes[i]);
            }
        }
        return root;
    }
    
    private void setHeights(Node root) {
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            Node node = stack1.pop();
            if (node.children.size() != 0) { // not leaf!
                stack2.push(node); // push all non-leaf nodes to stack2 for processing later
                for (Node child: node.children) {
                    stack1.push(child);
                }
            }
        }
        while (!stack2.isEmpty()) {
            Node node = stack2.pop();
            for (Node child: node.children) {
                node.height = Math.max(node.height, child.height + 1);
            }
        }
    }
    
    private void calculateMaxDist(Node root) {
        int maxDepth1 = 0;
        int maxDepth2 = 0;
        for (Node child: root.children) {
            int maxDepth = child.height + 1;
            if (maxDepth >= maxDepth1) {
                maxDepth2 = maxDepth1;
                maxDepth1 = maxDepth;
            } else if (maxDepth > maxDepth2) {
                maxDepth2 = maxDepth;
            }
        }
        maxDist = Math.max(maxDist, maxDepth1 + maxDepth2);
    }
    
    public int solve(ArrayList<Integer> A) {
        Node[] nodes = new Node[A.size()];
        Node root = constructGraph(nodes, A);
        setHeights(root);
        for (Node node: nodes) {
            calculateMaxDist(node);
        }
        
        return maxDist;
    }
}

Solution3:

first BFS to find leaf node that is the deepest, then do another bfs from that node to find the largest distance

public class Solution {
    private void bfs(int root, Map<Integer, List<Integer>> edges, int[] fur, int[] max) {
        int[] dist = new int[edges.size()];
        Arrays.fill(dist, -1);
        dist[root] = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int parent = queue.poll();
            for (int child : edges.getOrDefault(parent, new ArrayList<>())) {
                if (dist[child] == -1) {
                    queue.offer(child);
                    dist[child] = dist[parent] + 1;
                }
            }
        }
        for (int i = 0; i < dist.length; i ++) {
            int d = dist[i];
            if (d > max[0]) {
                max[0] = d;
                fur[0] = i;
            }
        }
    }
    
    public int solve(ArrayList<Integer> A) {
        int n = A.size();
        Map<Integer, List<Integer>> edges = new HashMap<>();
        int root = -1;
        for (int i = 0; i < n; i ++) {
            int parent = A.get(i);
            int child = i;
            List<Integer> children = edges.getOrDefault(parent, new ArrayList<>());
            children.add(child);
            edges.put(parent, children);

            if (parent != -1) {
                List<Integer> children2 = edges.getOrDefault(child, new ArrayList<>());
                children2.add(parent);
                edges.put(child, children2);
            }
            
            if (parent == -1) {
                root = i;
            }
        }
        int[] fur = new int[]{0};
        int[] max = new int[]{0};
        bfs(root, edges, fur, max);
        bfs(fur[0], edges, fur, max);
        return max[0];
    }
}