Tuesday 22 September 2015

Find depth of tree from parent array

Problem

A tree is represented by an array of integer where arr[i] represents the parent of ith node. arr[i]=-1 for root node. Find the depth of that tree

Solution

We can start with any node and calculate its depth by recursive function and then return the maximum depth among all the nodes. But in this process we will calculate the value of some nodes multiple times. So we will keep a depthArray which will keep track of the values for nodes that has been calculated once. Because of this memoization we will calculate each node exactly once. So the complexity is O(n)

Code

public class DepthFromParrentArray {
  public static void main(String[] args) {
    int[] parentArray = {3, -1, 3, 1, 5, 1, 0, 4, 2, 6};
    System.out.println(findDepth(parentArray));
  }

  private static int findDepth(int[] parentArray) {
    int[] depthArray = new int[parentArray.length + 1];
    for (int i = 0; i < parentArray.length; ++i) {
      findDepthRecursive(depthArray, parentArray, i);
    }
    return depthArray[parentArray.length];
  }


  private static int findDepthRecursive(int[] depth,
      int[] parentArray, int i) {
    if (i == -1) {
      return 0;
    }
    if (depth[i] != 0) {
      return depth[i];
    }
    depth[i] = 1 + findDepthRecursive(depth, parentArray,
        parentArray[i]);
    if (depth[i] > depth[parentArray.length]) {
      depth[parentArray.length] = depth[i];
    }
    return depth[i];
  }
}

No comments:

Post a Comment