gistfile1.txt

1.
A tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1. 
The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes
that node with id k is the root. For ex:


3 3 3 -1 2
0 1 2 3 4
In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4. 

Given such an array, find the heig  ht of the tree.

keyword:

a tree - children maybe > 2
0 - N - 1, total N nodes 
customize array[i] - i - node id, array[i] is node id i's parent 
-1 is special: root node

ask: given such an array, find the hight of the tree

3 3 3 -1 2 
0 1 2 3  4
reconstruct:
 parent <- child
  3 <-  0
  3 <-  1
  3 <-  2
  -1 <- 3  root
  2 <- 4
  above height of tree is 3
  0 -> 3 -> -1 -> 0 -> height[0] = 2, height[3] = 1, 
  1 -> 3 -> -1  -> 1 + height[3] = 2
  2 -> 3 -> - 1 -> 1 + height[3] = 2
  3 -> -1
  4 -> 2 -> 3-> -1  
  line 36 -> 3   brute force solution O(n * height of tree)
  line 34, 2 -> 3
  
  public static int FindHeightOfTree(int[] numbers)  // indexWithParentId
  {
     if(numbers == null)
     	return new int[0]; 
      
     var length = numbers.Length; 
     
     var heightIds = new int[length]; 
     for(int index = 0; index < length; index++)
     {
        if(heightIds[index] > 0)
          continue; 
          
        // find the path for id = index, save height along the path for each id
        //3 3 3 -1 2 
				//0 1 2 3  4
        var iterate = index; // 0
        var pathLength = 0;
        var pathList = new List<int>();
        // index = 3
        // iterate = index = 3
        // numbers[iterate] = -1
        while(iterate != -1)  // deadloop - no problem   -> 
        {
        	var visit = numbers[iterate];  // 3
          iterate = visit; // 3
          
          // height -> no more loop -> exit 
          if(height[visit] > 0) // 
          {
            pathLength += height[visit];
            break;
          }
            
          pathList.Add(visit); // 3
          pathLength++;
        }
        
        // add one more while loop -> replace the list 
        
        heightIds[index] = pathLength;
        for(int i = 0; i < pathList.Length; i++)
        {
          if(height[pathList[i]] != 0)  // duplicate -> more than O(n)
        		height[pathList[i]] = pathLength - i; 
        }
     }
     
     return heightIds.Max();
  }
  
  
-1 0 1 2 3
0  1 2 3 4

0 - > -1 
1 -> 0 -> -1 
2 -> 1 -> look up height
3 -> 2 -> look up height
4->3 -> look up height