Given only parent array find height of a genric tree | java implementation

Hello friends,

I recently came across an interesting question on Tree. The problem statement is as below:

Suppose a generic tree has N nodes and nodes are named using the numbers between inclusive range 0 to N-1. An array of Integers, named 'parent' , is given, such that  'parent[i]' represents name of the parent node for node-i. For the root value stored in 'parent' array is -1. Find the height of the Tree.

Friends Points to note are :

1. Tree is generic and not necessary a Binary tree.
2. Only information we have is of Parents of each node.
3. Root is not necessarily at position 0, as it is not mentioned in the problem statement.

Lets see this with a diagram.



Lets see the parent array for this tree

int[] parent = {6,6,6,-1,3,0,3};

Friends to solve this we will first compute the depth of each node and memorize it. Using above information, depth of any node can be simply calculated by adding 1 to the depth of its parent. The node at maximum depth will be the height of the tree.

Lets see the implementation in Java for solving this problem

 

package generictree;
/**
 * 
 * @author Krishna.k
 * 
 *         Suppose a generic tree has N nodes and nodes are named using the
 *         numbers between inclusive range 0 to N-1. An array of Integers, named
 *         'parent' , is given, such that 'parent[i]' represents name of the
 *         parent node for node-i. For the root value stored in 'parent' array
 *         is -1. Find the height of the Tree.
 *
 */
public class FindHeightGivenParentArray {
    public static void main(String[] args) {
        int[] parent = { 6, 6, 6, -1, 3, 0, 3 };
        int N = parent.length;
        System.out.println("height of tree is " + getHeightOfTree(parent, N));
    }

    public static int getHeightOfTree(int[] parent, int N) {
        int[] depths = new int[N];
        int maxDepth = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            if (depths[i] == 0) {
                int depthOfIthNode = findDepthOfIthNode(parent, depths, i);
                if (maxDepth < depthOfIthNode) {
                    maxDepth = depthOfIthNode;
                }
            }
        }
        return maxDepth;
    }

    public static int findDepthOfIthNode(int[] parent, int[] depths, int i) {
        if (depths[i] != 0) {
            return depths[i];
        }
        if (parent[i] == -1) {
            depths[i] = 1;
            return depths[i];
        }
        depths[i] = findDepthOfIthNode(parent, depths, parent[i]) + 1;
        return depths[i];
    }
}

The Output for the above program on console is :
height of tree is 4