Create a binary tree from an array of integers .


Write a function that given an array representation of a binary tree will convert it into a typical tree format.
The following is a visual representation of expected input and output:

Input: [7, 3, 9, 2, 4, 8, 10,11,12,13,14]
Output:
7
/ \
3 9
/\ /\
2 4 8 10

One way to build a tree is that we know that array is like a breadth first traversal . So the series it appears is the same order we need to create tree. Also other property of tree is for a node at index “index” , left child is [2*index+1] and right child is [2*index+2].

public Node createTree(Integer[] array){
        
        if(array == null || array.size == 0)
         return null;
     	Node n = array[0];
     	Queue queue =new Queue();
     	queue.add(n);
        int count = 1;
     	while(count < array.length || !queue.isEmpty()){
     		n.left = new Node(array[count++]);
     		queue.add(n);
                if(count < array.length){
                  n.right = new Node(array[count++])
     		  queue.add(n.right)
               }    	
     	}
     return n;
     }
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