Q4_1.java

public class Q4_1{
	public static void main(String[] args){
		BST<Integer> tree = new BST<Integer>(new TreeNode(15,null,null));
		for(int i = 9; i<20; i=i+10){
			tree.insert(i);
			tree.insert(i-2);
			tree.insert(i+2);
		}
		tree.insert(6);
		tree.insert(8);
		tree.insert(5);
		System.out.println(isBalanced(tree.root()));
		
		
	}
	static boolean isBalanced(TreeNode n){
		if(countHeight(n)== -1)
			return false;
		else return true;
	}
	
	static int countHeight(TreeNode n){
		if(n == null)
			return 0;
		else{
			int leftHeight = countHeight(n.left);
			int rightHeight= countHeight(n.right);
			if(leftHeight >-1 && rightHeight>-1){
				//System.out.println(leftHeight + ""+rightHeight);
				return Math.abs(leftHeight-rightHeight) > 1 ? -1: Math.max(leftHeight, rightHeight)+1;
			}
			else return -1;
		}
	}
	
}

class TreeNode<Item>{
	Item value;
	TreeNode left;
	TreeNode right;
	TreeNode(Item val,TreeNode o1, TreeNode o2){
		value = val;
		left = o1;
		right = o2;
	}
}
class BST<T extends Comparable<T>> {
    private TreeNode<T> root = null;
 
    public BST(TreeNode<T> r) {
	root = r;
    }
 
    public TreeNode<T> root() {
	return root;
    }
    
    public void insert(T key) {
	if(root == null) root = new TreeNode<T>(key, null, null);
	TreeNode<T> cur = root;
	TreeNode<T> prev = null;
	while(cur != null) {
	    prev = cur;
	    if(key.compareTo(cur.value) <= 0)
		cur = cur.left;
	    else
		cur = cur.right;
	}
	
	if(key.compareTo(prev.value) <= 0)
	    prev.left = new TreeNode<T>(key, null, null);
	else
	    prev.right = new TreeNode<T>(key, null, null);
    }
}