Big Data Analytics:Deep Findings

Question
You are given a tree with N nodes. Each node is given an integer value from 0 to N­1 . Tree given as an input will be an array of parent nodes.
You need to find following (all mandatory):
1 . The depth of the tree (Aim for O(N))
2. Maximum number of children for any node in whole tree (Aim for O(N))
3. Nearest Common Ancestor for two given nodes (Aim for O(log(N)))
INPUT FORMAT
First line has the value of N
Second line has list of N values where the number at index ‘i’ is the parent of node ‘i’. The parent of root is
­1 . ( The index has the range [0,N­1 ] )
Third line contains two integers within the range of [0,N­1 ] whose common ancestor you have to find.
OUTPUT FORMAT
First line has the depth of the tree. Second line has the max children.
Third has the nearest common ancestor to two
given nodes n1 and n2.

SAMPLE INPUT 1
5­
-1 0 1 2 1
3 4
SAMPLE OUTPUT 1
4

2

1
SAMPLE INPUT 2
11
3 3 3 6 0 4 -­1 6 7 7 7
5 2
SAMPLE OUTPUT 2
5

3

3

package ProgI;

public class DeepFindings {
 static int depth = 0;


 static public int maxChildren(int tree[]) {
  int arr[] = new int[tree.length];
  int max = 0;
  for (int i = 0; i < tree.length; i++) {
   if (tree[i] != -1) {
    arr[tree[i]]++;
    if (arr[tree[i]] > max)
     max = arr[tree[i]];
   }

  }
  return max;

 }

 static public int parentPath(int tree[], int a, int b) {
  int j = 0;
  int APath[] = new int[depth], BPath[] = new int[depth];
  while (a != -1) {
   APath[j] = tree[a];
   a = tree[a];
   j++;
  }
  ;
  int i = 0;
  while (b != -1) {
   BPath[i] = tree[b];
   b = tree[b];
   i++;

  }
  ;

  for (int k = 0; k < depth; k++) {
   i--;
   j--;
   if (i >= 0 && j >= 0 && APath[j] == BPath[i])
    continue;
   else
    return BPath[i + 1];

  }

  return 0;
 }

 static public void maxDepth(int tree[], int i, int val) {
  boolean flag = false;

  for (int j = 0; j < tree.length; j++) {
   if (tree[j] == val) {

    val = j;

    maxDepth(tree, i + 1, val);

    flag = true;

   }

  }
  if (!flag) {

   if (i >= depth)
    depth = i;

  }

  return;
 }

 public static void main(String[] args) {
  // input 1
  System.out.println("INPUT 1");
  int parrents[] = { 3, 3, 3, 6, 0, 4, -1, 6, 7, 7, 7 };
  maxDepth(parrents, 0, -1);// worst case complexity O(N)
  System.out.println(depth);
  System.out.println(maxChildren(parrents));// worst case complexity O(N)
  System.out.println(parentPath(parrents, 5, 2));// worst case complexity
              // O(N)
  // input 2
  System.out.println("INPUT 2");
  depth = 0;
  int parrents2[] = { -1, 0, 1, 2, 1 };
  maxDepth(parrents2, 0, -1);// worst case complexity O(N)
  System.out.println(depth);
  System.out.println(maxChildren(parrents2)); // worst case complexity
             // O(N)
  System.out.println(parentPath(parrents2, 3, 4));// worst case complexity
              // O(N)

 }

}

OUTPUT 1
5
3
3
OUTPUT 2
4
2
1