RSS

Find the height of the tree

01 Jan

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

It would be good to solve this problem in O(n).

Advertisements
 
5 Comments

Posted by on January 1, 2010 in Algorithms

 

Tags: , , ,

5 responses to “Find the height of the tree

  1. Guru

    April 6, 2010 at 6:14 am

    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.

     
  2. ranganathg

    April 7, 2010 at 6:36 pm

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

     
  3. chiku

    November 16, 2010 at 5:49 am

    @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!).

     
  4. chiku

    November 16, 2010 at 6:09 am

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

     
  5. ranganathg

    November 16, 2010 at 10:18 am

    @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.

     

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: