Diameter in a Generic Tree

I/P: 

20 10 20 -50 -1 60 -1 -1 30 -70 -1 80 -1 90 -1 -1 40 -100 -1 -1 -1

O/P: 4

Diameter = max. distance between 2 nodes

Approach:

We need to maximize the number of edges between any two nodes to calculate diameter. To be noted that to maximize the number of edges we have to always consider the leaf nodes. 

Now we wish to find a diameter that passes through our current node. This can be found by adding the deepest subtree and second deepest subtree and adding 2 to their sum. 

Getting the deepest and second deepest subtree ensures that we are taking the maximum possible edges from the current node and 2 is added to link both the leaves. 

Now we can recurse this approach for every node in our tree as our diameter need not always pass through the root node. So at each node, we calculate the diameter from the current node and compare it with the global maximum and then we return the height of our subtree which can, later on, be used by any ancestor nodes to calculate their diameter and height.

package pep.Day31;

import java.io.*;
import java.util.*;


public class Diameter_Of_GenericTree {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        Node root = construct(arr);
        // write your code here
        calculateDiameterReturnHeight(root);
        System.out.println(max_diameter);
    }

    static int max_diameter = 0;

    private static int calculateDiameterReturnHeight(Node node) {
        int maximum_height = -1;
        int second_maximum_height = -1;
        for (int i = 0; i < node.children.size(); i++) {
            Node child = node.children.get(i);
            int childHeight = calculateDiameterReturnHeight(child);
            if (childHeight > maximum_height) {
                second_maximum_height = maximum_height;
                maximum_height = childHeight;
            } else if (childHeight > second_maximum_height) {
                second_maximum_height = childHeight;
            }
        }
        int diameter = maximum_height + second_maximum_height + 2;
        max_diameter = Math.max(diameter, max_diameter);

        maximum_height += 1;
        return maximum_height;
    }

}

Time Complexity: O(n)

The time complexity for the function is linear as tree traversal is involved which is linear in terms of time complexity.

Space Complexity: O(h)

The space complexity for the function is proportional to the height of the generic tree due to the recursion stack.