HackerRank Journey Scheduling Problem Solution

        #include <stdio.h>
        #include <stdlib.h>
        #include <string.h>
        typedef struct _node{
          int x;
          int w;
          struct _node *next;
        } lnode;
        void insert_edge(int x,int y,int w);
        void dfs1(int x);
void dfs2(int x,int y);
int max(int x,int y);
        int h[100000],sh[100000],l[100000],u[100000],trace[100000];
        lnode *table[100000]={0};
         
        int main(){
          int N,M,x,y,i;
            scanf("%d%d",&N,&M);
            for(i=0;i<N-1;i++){
              scanf("%d%d",&x,&y);
              insert_edge(x-1,y-1,1);
            }
            memset(trace,0,sizeof(trace));
            dfs1(0);
            memset(trace,0,sizeof(trace));
            dfs2(0,-1);
            for(i=0;i<M;i++){
              scanf("%d%d",&x,&y);
              printf("%lld\n",max(h[x-1],u[x-1])+(y-1)*(long long)l[0]);
            }
          return 0;
        }
        void insert_edge(int x,int y,int w){
          lnode *t=malloc(sizeof(lnode));
          t->x=y;
          t->w=w;
          t->next=table[x];
          table[x]=t;
          t=malloc(sizeof(lnode));
          t->x=x;
          t->w=w;
          t->next=table[y];
          table[y]=t;
          return;
        }
        void dfs1(int x){
          lnode *p;
          trace[x]=1;
          h[x]=sh[x]=l[x]=0;
          for(p=table[x];p;p=p->next)
            if(!trace[p->x]){
              dfs1(p->x);
              if(h[p->x]+p->w>=h[x]){
                sh[x]=h[x];
                h[x]=h[p->x]+p->w;
              }
              else if(h[p->x]+p->w>sh[x])
                sh[x]=h[p->x]+p->w;
              if(l[p->x]>l[x])
                l[x]=l[p->x];
            }
          if(h[x]+sh[x]>l[x])
            l[x]=h[x]+sh[x];
          return;
        }
        void dfs2(int x,int y){
          lnode *p;
          trace[x]=1;
if(y==-1)
u[x]=0;
else
if(h[y]==h[x]+1)
u[x]=max(u[y]+1,sh[y]+1);
else
u[x]=max(u[y]+1,h[y]+1);
          for(p=table[x];p;p=p->next)
            if(!trace[p->x])
              dfs2(p->x,x);
          return;
        }
int max(int x,int y){
  return (x>y)?x:y;
}

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define pb push_back

int ri()
{
  int x;
  scanf("%d", &x);
  return x;
}

const int N = 100000;
vector<int> e[N];
int s[N], ss[N], far[N];

void dfs(int u, int p)
{
  for (int v: e[u])
    if (v != p) {
      dfs(v, u);
      if (s[v]+1 > ss[u]) {
        ss[u] = s[v]+1;
        if (ss[u] > s[u])
          swap(ss[u], s[u]);
      }
    }
}

void dfs2(int u, int p, int up)
{
  far[u] = max(s[u], up);
  for (int v: e[u])
    if (v != p)
      dfs2(v, u, max(s[v]+1 == s[u] ? ss[u] : s[u], up) + 1);
}

int main()
{
  int n = ri(), m = ri();
  REP(i, n-1) {
    int u = ri()-1, v = ri()-1;
    e[u].pb(v);
    e[v].pb(u);
  }
  dfs(0, -1);
  dfs2(0, -1, 0);
  ll diameter = *max_element(far, far+n);
  while (m--) {
    int x = ri()-1, y = ri();
    printf("%lld\n", (y-1)*diameter+far[x]);
  }
}

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'journeyScheduling' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. 2D_INTEGER_ARRAY roads
     *  3. 2D_INTEGER_ARRAY journeys
     */

    class LCA
    {
        private int[] _height;
        private List<int> _euler;
        private int[] _first;
        private int[] _segtree;
        private bool[] _visited;
        private int n;
        private int _diameter;
        private int _d1;
        private int _d2;


        public LCA(List<int>[] adj, int root = 0)
        {
            n = adj.Length;
            _height = new int[n];
            _first = new int[n];
            _euler = new List<int>(n*2);
            _visited = new bool[n];
            _diameter = 0;
            _d1 = root;
            
            DfsEuler(adj, root);
            _visited = new bool[n];
            _d2 = _d1;
            _diameter = 0;
            DfsD2(adj, _d1);

            int m = _euler.Count;
            _segtree = new int[m*4];
            Build(1, 0, m - 1);
        }

        private void DfsEuler(List<int>[] adj, int node, int h = 0)
        {
            _visited[node] = true;
            _height[node] = h;
            _first[node] = _euler.Count;
            _euler.Add(node);
            if (h > _diameter)
            {
                _d1 = node;
                _diameter = h;
            }
            foreach (var to in adj[node])
            {
                if (!_visited[to])
                {
                    DfsEuler(adj, to, h+1);
                    _euler.Add(node);
                }
            }
        }
        private void DfsD2(List<int>[] adj, int node, int h = 0)
        {
            _visited[node] = true;
            if (h > _diameter)
            {
                _d2 = node;
                _diameter = h;
            }
            foreach (var to in adj[node])
            {
                if (!_visited[to])
                {
                    DfsD2(adj, to, h+1);
                }
            }
        }
        private void Build(int node, int b, int e)
        {
            if (b == e)
            {
                _segtree[node] = _euler[b];
            }
            else
            {
                var mid = (b + e) / 2;
                Build(node * 2, b, mid);
                Build(node*2+1, mid+1, e);
                int l = _segtree[node * 2];
                int r = _segtree[node * 2 + 1];
                _segtree[node] = (_height[l] < _height[r]) ? l : r;
            }
        }

        private int Query(int node, int b, int e, int L, int R)
        {
            if (b > R || e < L) return -1;
            if (b >= L && e <= R)
                return _segtree[node];
            int mid = (b + e) / 2;
            int left = Query(node * 2, b, mid, L, R);
            int right = Query(node * 2 + 1, mid + 1, e, L, R);
            if (left == -1) return right;
            if (right == -1) return left;
            return _height[left] < _height[right] ? left : right;
        }

        int Lca(int u, int v)
        {
            int left = _first[u];
            int right = _first[v];
            if (left > right)
            {
                var val = left;
                left = right;
                right = val;
            }

            return Query(1, 0, _euler.Count - 1, left, right);
            
        }

        public int Distance(int u, int v)
        {
            var lca = Lca(u, v);
            return _height[u] + _height[v] - 2 * _height[lca];
        }

        public int DistanceToDiameter(int node)
        {
            return Math.Max(Distance(node, _d1), Distance(node, _d2));
        }

        public int Diameter => _diameter;

    }

    private static (int, int) FarthestNode(Dictionary<int, List<int>> al, int node)
    {
        var s = new Stack<(int,int, int)>();//node, distance, parentNode
        var max = (node, 0);
        s.Push((node, 0, node));
        while (s.Count > 0)
        {
            var cnode = s.Pop();
            var children = al[cnode.Item1].Where(n => n != cnode.Item3)
                .Select(n => (n, cnode.Item2 + 1, cnode.Item1)).ToList();
            if(children.Count>0 && children[0].Item2>max.Item2)
            {
                max = (children[0].Item1, children[0].Item2);
            }

            foreach (var child in children)
            {
                s.Push(child);
            }
            
        }
        return max;
    }

    public static List<long> journeyScheduling(int n, List<List<int>> roads, List<List<int>> journeys)
    {
        var adj = new List<int>[n];
        var nodeToBorder = new Dictionary<int, int>();

        foreach (var road in roads)
        {
            var from = road[0]-1;
            var to = road[1]-1;
            if (adj[from]!=null)
            {
                adj[from].Add(to);
            }
            else
            {
                adj[from] = new List<int> {to};
            }

            if (adj[to]!=null)
            {
                adj[to].Add(from);
            }
            else
            {
                adj[to] = new List<int> {from};
            }
        }

        //var r = new Random(1978).Next(n);

        var lca = new LCA(adj);
        

        var results = journeys.Select(joureney =>
        {
            if (nodeToBorder.ContainsKey(joureney[0]))
            {
                return (long)nodeToBorder[joureney[0]] + (long)(joureney[1] - 1) * lca.Diameter;
            }

            var toBorder = lca.DistanceToDiameter(joureney[0] - 1);
            
            nodeToBorder[joureney[0]] = toBorder;
            
            return (long)toBorder + (long)(joureney[1] - 1) * lca.Diameter;
        }).ToList();
        return results;
    }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

        int n = Convert.ToInt32(firstMultipleInput[0]);

        int m = Convert.ToInt32(firstMultipleInput[1]);

        List<List<int>> roads = new List<List<int>>();

        for (int i = 0; i < n - 1; i++)
        {
            roads.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(roadsTemp => Convert.ToInt32(roadsTemp)).ToList());
        }

        List<List<int>> journeys = new List<List<int>>();

        for (int i = 0; i < m; i++)
        {
            journeys.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(journeysTemp => Convert.ToInt32(journeysTemp)).ToList());
        }

        List<long> result = Result.journeyScheduling(n, roads, journeys);

        textWriter.WriteLine(String.Join("\n", result));

        textWriter.Flush();
        textWriter.Close();
    }
}

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
    private static class Node {
        final int index;
        final Set<Node> neighbors = new HashSet<>();

        Node(int index) {
            this.index = index;
        }
    }

    /*
     * Complete the journeyScheduling function below.
     */
    static long[] journeyScheduling(int n, int[][] roads, int[][] journeys) {
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i);
        }
        for (int[] road : roads) {
            nodes[road[0] - 1].neighbors.add(nodes[road[1] - 1]);
            nodes[road[1] - 1].neighbors.add(nodes[road[0] - 1]);
        }

        Node start = findEnd(nodes[0]);
        Node end = findEnd(start);
        List<Node> diameterPath = findPath(start, end);
        int diameter = diameterPath.size() - 1;
        int[] distances = new int[n];
        if ((diameter & 1) == 0) {
            maxDistances(diameterPath.get(diameter/2), null, diameter/2, distances);
        } else {
            maxDistances(diameterPath.get(diameter/2), diameterPath.get(diameter/2 + 1), diameter/2 + 1, distances);
            maxDistances(diameterPath.get(diameter/2 + 1), diameterPath.get(diameter/2), diameter/2 + 1, distances);
        }
//        System.out.println(String.format("Diameter: %d, distances: %s", diameter, Arrays.toString(distances)));

        long[] results = new long[journeys.length];
        for (int i = 0; i < journeys.length; i++) {
            results[i] = distances[journeys[i][0] - 1] + ((long) diameter)*(journeys[i][1] - 1);
        }
        return results;
    }

    private static class State {
        final Node cur;
        final Node prev;
        final Iterator<Node> children;
        final int distance;

        State(Node cur, Node prev, int distance) {
            this.cur = cur;
            this.prev = prev;
            this.children = cur.neighbors.iterator();
            this.distance = distance;
        }
    }

    private static Node findEnd(Node cur) {
        Node end = cur;
        int maxDistance = -1;
        Deque<State> stack = new ArrayDeque<>();
        stack.addFirst(new State(cur, null, 0));
        while (!stack.isEmpty()) {
            State state = stack.peekFirst();
            if (state.children.hasNext()) {
                Node child = state.children.next();
                if (child == state.prev) {
                    // Do nothing
                } else if (child.neighbors.size() == 1) {
                    if (state.distance > maxDistance) {
                        maxDistance = state.distance;
                        end = child;
                    }
                } else {
                    stack.addFirst(new State(child, state.cur, state.distance + 1));
                }
            } else {
                stack.removeFirst();
            }
        }
        return end;
    }

    private static List<Node> findPath(Node cur, Node goal) {
        Deque<State> stack = new ArrayDeque<>();
        stack.addFirst(new State(cur, null, 0));
        while (stack.peekFirst().cur != goal) {
            State state = stack.peekFirst();
            if (state.children.hasNext()) {
                Node child = state.children.next();
                if (child != state.prev) {
                    stack.addFirst(new State(child, state.cur, 0));
                }
            } else {
                stack.removeFirst();
            }
        }

        List<Node> path = new ArrayList<>();
        while (!stack.isEmpty()) {
            path.add(stack.removeFirst().cur);
        }
        return path;
    }

    private static void maxDistances(Node cur, Node prev, int distance, int[] distances) {
        distances[cur.index] = distance;
        Deque<State> stack = new ArrayDeque<>();
        stack.addFirst(new State(cur, prev, distance));
        while (!stack.isEmpty()) {
            State state = stack.peekFirst();
            if (state.children.hasNext()) {
                Node child = state.children.next();
                if (child != state.prev) {
                    distances[child.index] = state.distance + 1;
                    stack.addFirst(new State(child, state.cur, state.distance + 1));
                }
            } else {
                stack.removeFirst();
            }
        }
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nm = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

        int n = Integer.parseInt(nm[0]);

        int m = Integer.parseInt(nm[1]);

        int[][] roads = new int[n-1][2];

        for (int roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
            String[] roadsRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            for (int roadsColumnItr = 0; roadsColumnItr < 2; roadsColumnItr++) {
                int roadsItem = Integer.parseInt(roadsRowItems[roadsColumnItr]);
                roads[roadsRowItr][roadsColumnItr] = roadsItem;
            }
        }

        int[][] journeys = new int[m][2];

        for (int journeysRowItr = 0; journeysRowItr < m; journeysRowItr++) {
            String[] journeysRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            for (int journeysColumnItr = 0; journeysColumnItr < 2; journeysColumnItr++) {
                int journeysItem = Integer.parseInt(journeysRowItems[journeysColumnItr]);
                journeys[journeysRowItr][journeysColumnItr] = journeysItem;
            }
        }

        long[] result;
//        try {
            result = journeyScheduling(n, roads, journeys);
/*        } catch (StackOverflowError e) {
            result = new long[1];
        }*/

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

function processData(input) {
    
    var inputValues=input.replace(/\n/g," ").split(" ");

    var N = parseInt(inputValues[0]);   //Number of Cities
    var M = parseInt(inputValues[1]);   //Number of possible journeys
    
    //bi-directional road between the cities with numbers X and Y
    var X = [];
    var Y = [];
    for (var i=0;i<N-1;i++) {
        X[i] = parseInt(inputValues[i*2+2]);
        Y[i] = parseInt(inputValues[i*2+3]);
    }
    
    //starting city V and the total number of cities to be visited K 
    var V = [];
    var K = [];
    for (var j=0;j<M;j++) {
        V[j] = parseInt(inputValues[j*2+N*2]);
        K[j] = parseInt(inputValues[j*2+N*2+1]);
    }

    //Convert edge list to adjacency list
    var graph = edgeToAdjList(X,Y);
    
    var singleNodes = 0;
    for (var key in graph) {
        if (graph.hasOwnProperty(key)) {
            if (graph[key].adjNodes.length == 1)       
                 singleNodes += 1;  
        }
    } 
    
    var alternativeMethod = false;    
    
    if(singleNodes/N > 0.9)    
        alternativeMethod = true;   
    
    if(alternativeMethod) {
        var distances = {};
        var initialNode = 1;
        
        var diameter = treeDiameter(graph, initialNode, 0, initialNode, distances, initialNode);
            
        var edge1 = initialNode;
        for (var key in distances[initialNode]) {
            if (distances[initialNode].hasOwnProperty(key)) {
                if (distances[initialNode][key]>distances[initialNode][edge1])       
                    edge1 = key;  
            }
        }     
        
        treeDiameter(graph, edge1, 0, edge1, distances, edge1);
        
        var edge2=edge1;
        for (var key in distances[edge1]) {
            if (distances[edge1].hasOwnProperty(key)) {
                if (distances[edge1][key]>distances[edge1][edge2])       
                    edge2 = key;  
            }
        }  
        
        treeDiameter(graph, edge2, 0, edge2, distances, edge1);
    

    
        //Calculate trip distances
        for(i=0;i<M;i++) {
            //console.log("Start of trip...");
            var initialCity = V[i];      //City of departure
            var tripsPending = K[i];     //Number of trips
            var totalDistance = 0;       //Distance accumulated during total trip
            
            
            var firstTripDistance = Math.max(distances[edge1][initialCity],distances[edge2][initialCity]);
    
            
            totalDistance = firstTripDistance + (diameter-1)*(tripsPending-1);
    
            
            console.log(totalDistance);
        }
    }
    else {
        var edgeDistances = {};
         
        //var edges = findTreeEdges(graph,edgeDistances);
        //var diameter = edgeDistances[edges[0]].maxDistance;
        
        var edges = findTreeDistances(graph,edgeDistances);
        
        var diameter = edgeDistances[edges[0]].maxDistance;      
        
        //Calculate trip distances
        for(i=0;i<M;i++) {
            //console.log("Start of trip...");
            var initialCity = V[i];      //City of departure
            var tripsPending = K[i];     //Number of trips
            var totalDistance = 0;       //Distance accumulated during total trip
            
            
            var firstTripDistance = 0;
            for(var j=0;j<edges.length;j++) {
                if(edgeDistances[edges[j]][initialCity]>firstTripDistance) {
                    firstTripDistance = edgeDistances[edges[j]][initialCity];
                }
            }
            
            totalDistance = firstTripDistance + diameter*(tripsPending-1);
    
            
            console.log(totalDistance);
            
        }        
    }
   

} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});




function edgeToAdjList(X,Y) {
    var graph = {};
    
    //Loop through the edges list
    for (var i=0;i<X.length;i++) {
        //Check for X if node exists in graph, otherwise create it
        if (graph[X[i]]) {
            graph[X[i]].adjNodes.push(Y[i]);
        } else {
           graph[X[i]] = {}; 
           graph[X[i]].adjNodes = [Y[i]];
        }
        //Check for Y if node exists in graph, otherwise create it        
        if (graph[Y[i]]) {
            graph[Y[i]].adjNodes.push(X[i]);
        } else {
            graph[Y[i]] = {};             
            graph[Y[i]].adjNodes = [X[i]];
        }
    }
    return graph;   
}     



function bfs(adjlist, root) { 

    //Add distance and parent objects to every entry in the adjacency list
    for (var key in adjlist) {
        if (adjlist.hasOwnProperty(key)) {
            adjlist[key].distance = Infinity;       
            adjlist[key].parent = null;  
        }
    }    
    
    var Q = [];      
    
    adjlist[root].distance = 0;
    Q.push(adjlist[root]);
    
    //Calculate distances for every node in the graph versus the root node
    while(Q.length) {
        var current = Q.shift();
        for (var i=0;i<current.adjNodes.length;i++) {
            var n = adjlist[current.adjNodes[i]];
            if (!isFinite(n.distance)) {
                n.distance = current.distance + 1;
                n.parent = current;
                Q.push(n);
            }    
        }
      
        
    }  
    
    //Loop through the graph to find the nodes with further distance
    var furthestNodes = [];
    var maxDistance = 0;
    var dist = {};
    for (var key in adjlist) {
        if (adjlist.hasOwnProperty(key)) {
            dist[key] = adjlist[key].distance
            if (adjlist[key].distance > maxDistance) {
                maxDistance = adjlist[key].distance;
                furthestNodes = [key];              
            }
            else if (adjlist[key].distance == maxDistance) {
                furthestNodes.push(key);
            }
        }
    } 
    
    //Delete parent and distance properties
    for (var key in adjlist) {
        if (adjlist.hasOwnProperty(key)) {
            delete adjlist[key].distance;       
            delete adjlist[key].parent;
        }
    }  
    
    dist["furthestNodes"] = furthestNodes;
    dist["maxDistance"] = maxDistance;
        
    return dist;

};


function findTreeEdges(graph, distances) {
    
    var edges = [];
    var startingNode = 1;   //Assign node 1 as initial node
    
    //Calculate furthest edges from Node 1 as starting.point
    var initial = bfs(graph,startingNode);   
    
    var startingEdges = initial.furthestNodes   //Initial edges
    
    var E = [];      

    for(var i=0;i<Math.min(startingEdges.length,1);i++) {
        E.push(startingEdges[i]);
    }

    
    //Calculate distances for every node in the graph versus the root node
    while(E.length) {
        var current = E.shift();
        if(!distances[current]) {
            distances[current] = bfs(graph,current);
        }
        for (var i=0;i<Math.min(distances[current].furthestNodes.length,1);i++) {
            var n = distances[current].furthestNodes[i];
                if (!edges.includes(n)) {
                    edges.push(n);
                    E.push(n);
                }    
        }
            
    }  

    return edges;

};


function findTreeDistances(graph, distances) {
    var startingNode = 1;   //Assign node 1 as initial node
    
    var edges = [];
    
    //Calculate furthest edges from Node 1 as starting.point
    distances[startingNode] = bfs(graph,startingNode); 
 
 
    var edge1 = distances[startingNode].furthestNodes[0];  //Edge node
        
    //Calculate distances for every node in the graph versus the edge node
    distances[edge1] = bfs(graph,edge1);
    
    if(distances[startingNode].maxDistance==distances[edge1].maxDistance) {
        edges = [startingNode,edge1]
    }
    else {
        var edge2 = distances[edge1].furthestNodes[0];  //Edge node
        distances[edge2] = bfs(graph,edge2);
        edges = [edge1,edge2];
    }
    
    return edges;

};


/*The second parameter is to store the height of tree.
   Initially, we need to pass a pointer to a location with value
   as 0. So, function should be used as follows:
 
   int height = 0;
   struct node *root = SomeFunctionToMakeTree();
   int diameter = diameterOpt(root, &height); */

function diameterOpt(graph, node, previousNode, height)
{
  /* lh --> Height of left subtree
     rh --> Height of right subtree */
  var children = graph[node].adjNodes;
    console.log("Node: " + node);
    console.log("AdjNodes: " + children);
    console.log("Previous Node: " + previousNode);
    
    
  if(children.indexOf(previousNode) > -1)
      children.splice(children.indexOf(previousNode),1);
 
      console.log("Children: " + children);   
      
      
  if(!children.length)
  {
     height = 0;
     return 0; /* diameter is also 0 */
  }      
    
  var heightArr = [];
  var diameterArr = [];  
  for(var i=0;i<children.length;i++) {
      heightArr[i] = 0;
      diameterArr[i] = 0;
  } 
  

  /* Get the heights of left and right subtrees in lh and rh
    And store the returned values in ldiameter and ldiameter */
    
  for(var i=0;i<children.length;i++) {      
      diameterArr[i] = diameterOpt(graph,children[i],node,heightArr[i]);
  }   
      
  /* Height of current node is max of heights of left and
     right subtrees plus 1*/
  height = Math.max(heightArr) + 1;

  var h1,h2 = 0;
  for(var i=0;i<heightArr[i].length;i++) {
      if(heightArr[i] > h1) {
          h2 = h1;
          h1 = heightArr[i]
      }
      else if(heightArr[i] > h2) {
          h2 = heightArr[i];
      }
  }       
    
    console.log("H1: " + h1);
  console.log("H2: " + h2);
  console.log("Array of diameters: " + diameterArr);    
    
  return Math.max(h1 + h2 + 1, Math.max(diameterArr));
}



 
/* Function to get diameter of a binary tree */
function treeDiameter(tree,node,previousNode, rootNode,distances, edge)
{
    
    if(previousNode==0) {
        distances[rootNode] = {};
        distances[rootNode][rootNode] = 0;
    }
    else {
        distances[rootNode][node] = distances[rootNode][previousNode] + 1;
    }
        
    var children = JSON.parse(JSON.stringify(tree[node].adjNodes));
    

        
    if(children.indexOf(previousNode) > -1)
        children.splice(children.indexOf(previousNode),1);
  
    
    if(!children.length) {
        return 1;
    }    
    else {
        /* get the height of sub-trees */
        var subtreeHeights = [];
        for(var i=0;i<children.length;i++) {
            subtreeHeights[i] = treeHeight(tree,children[i],node);
        }
        
     
        /* get the height of sub-trees */
        var subtreeDiameters = [];
        for(var i=0;i<children.length;i++) {          
            subtreeDiameters[i] = treeDiameter(tree,children[i],node, rootNode, distances, edge);
        }    
        
        /* Return max of following three
        1) Diameter of children subtrees
        2) Height of 2 max subtree  heights + 1 */
        
        var h1 = 0;
        var h2 = 0;
        if(subtreeHeights.length<2) {
            h1 = subtreeHeights[0];
            h2 = 0;
        } 
        else {
            for(var i=0;i<subtreeHeights.length;i++) {
                if(subtreeHeights[i] > h1) {
                    h2 = h1;
                    h1 = subtreeHeights[i];
                }
                else if(subtreeHeights[i] > h2) {
                    h2 = subtreeHeights[i];
                }
            } 
        }
        
        return Math.max(h1 + h2 + 1, Math.max.apply(Math,subtreeDiameters));
        
    }    
} 
 
/* UTILITY FUNCTIONS TO TEST diameter() FUNCTION */
 
/*  The function Compute the "height" of a tree. Height is the 
    number f nodes along the longest path from the root node 
    down to the farthest leaf node.*/
function treeHeight(tree,node,previousNode)
{    
    var c = JSON.parse(JSON.stringify(tree[node].adjNodes));
    if(c.indexOf(previousNode) > -1)
        c.splice(c.indexOf(previousNode),1);
    
    if(!c.length) {
        return 1;
    } else {
        var h = [];
        for (var i=0;i<c.length;i++) {
            h[i] = treeHeight(tree,c[i],node);      
        }

            
        /* If tree is not empty then height = 1 + max of subtree heights */   
        return 1 + Math.max.apply(Math,h);
    }
}