Leave a comment

Height of the binary tree stored in array.

Qus: A binary tree is stored in an array( a) such that a[i] is the parent of i. Suppose an element in array is 6, the parent of this element will be a[6]. The parent of the root is -1. It is not a binary search tree. Find the height of the tree.

Solution: Let’s think about it. Assume if we have given a binary tree ( forget that it is stored in an array) how can we find the height? We will traverse each branch from root to leaf and height of the tree would be the length of the longest branch. We could traverse from root to leaf because each node knows about its children and we can easily jump to its children.

Suppose if tree is constructed such that each node knows its parent, is it possible to calculate the height (assume we have information about the leaves) ? yes!!! now we need to traverse from each leaf to root and again height would be the length of longest path. Does second scenario resemble with our original problem??? It does, except one thing that we do not have any idea about the leaves. Look at the problem once again, it says if element is i than the parent of this element is a[i,] that means each node knows about its parent. Can’t we take the advantage of binary tree stored in an array and we have direct access to all the elements. Can’t we figure out what are the leaves of tree stored in array?

Lets take an example of such binary tree

array = { -1, 2, 0, 0, 5, 6, 7, 3}

Because parent of each element i will be a[i] and we know that leaf cannot be a parent so, can we figure out what are the leaves?? we can, see that at 1st index 2 is stored but 1 is not referred by any other block in the array, it means a[1] (2) is not the parent of any other element. This is the clue, we will figure out what are the indexes which is not stored in array, the element stored at those positions will be leaves. Once we get the children we can traverse till root as parent of root is -1.

one representation of binary tree stored in above array :

tree_stored_array

I am not giving the implementation but, an algorithm. Please let me know if you want an implementation for the same.

  1. height = 0 count = 0
  2. Traverse the array and insert each a[i] in hashmap
  3. for(i=0 array.length-1) do following
         If(i is not present in hashmap){
         // means a[i] is leaf and from this we will traverse till root
         j = a[i]
         count = 0
         While(a[j] !=-1){
            count++
            j = a[j];
         }
         If(count > height) height = count}
  4. Return height
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

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: