Tag: binary tree

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;
     }

Program to find whether the binary tree is BST ?


A binary tree is binary search tree (BST) if :

  • If the left subtree nodes value is less than the given node.
  • If the right subtree nodes value is greater than the give node
  • Both the left and right subtrees are BST.

public class BinaryTreeIsBST {

	public boolean IsBST(TreeNode node, int max, int min){

		if(node == null)
			return true;
		if(min < node.value && node.value > max){
			return IsBST(node.left,min,node.value) &&
                         IsBST(node.right,node.value,max);
		}
		return false;
	}
}