You are given an array of length N. The array stores information about an n-ary tree. And the n-ary tree has N-nodes numbered 0 – (N-1).The ith index in the array contains the parent nodes number j. Given this array find the height of the tree. The parent of the root is -1

The last element in the array will be the leaf of the highest sub-tree.
1. Initialize a variable lets say height =0;
2. Read the last element, it has the its parent value, lets say val.
3. array[val] will give the parent to parent of the last node. Increment the variable.
4. Do the same till you find the root -1;
5. The value of the height is the height of the tree.

@ranganath: I have O(n) time and O(n) space solution to this one. If there is a solution which uses constant space lemme know the existence of it (not the algorithm!).

Logic: Traverse the Array from the last.

The last element in the array will be the leaf of the highest sub-tree.

1. Initialize a variable lets say height =0;

2. Read the last element, it has the its parent value, lets say val.

3. array[val] will give the parent to parent of the last node. Increment the variable.

4. Do the same till you find the root -1;

5. The value of the height is the height of the tree.

Why is the last element in the array the leaf of the heighest sub tree?

@ranganath: I have O(n) time and O(n) space solution to this one. If there is a solution which uses constant space lemme know the existence of it (not the algorithm!).

@ranganath: actually I can do in O(n) time and O(1) space if I’m allowed to destroy array!

@chiku,

if you can share your solution, that would be great. My solution took O(n) time/extra space. This was my interview question at Trilogy.