gistfile1.java

public class ArrayToBST {


  public static void main( String[] args ) {


		int[] x = { 9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76 };
		BinarySearchTree t = new BinarySearchTree();


		SortedArrayToBST( t, x, 0, x.length - 1 );
		t.BSTTraverse();
		if ( t.isBalanced() )
			System.out.println( "Successfully built a balanced BST!" );
		else System.out.println( "You failed, please review your code!" );
	}


	public static void SortedArrayToBST( BinarySearchTree t, int[] x, int i, int j ) {
		int middle = ( int ) ( ( i + j ) / 2 );
		if ( i >=0 && j >= 0 && j >= i ) {
			t.BSTInsert( new TreeNode( x[ middle ] ) );
			SortedArrayToBST( t, x, i, middle - 1 );
			SortedArrayToBST( t, x, middle + 1, j );
		}
	}


}

gistfile2.java

public class BinarySearchTree {


  private TreeNode root;
	//private int height;


	public BinarySearchTree() {
		root = null;
	}


	public BinarySearchTree( TreeNode n ) {
		this.root = n;
	}


	public TreeNode getRoot() {
		return this.root;
	}


	public BinarySearchTree getLeftTree() {
		return new BinarySearchTree( this.root.getLeft() );
	}


	public BinarySearchTree getRightTree() {
		return new BinarySearchTree( this.root.getRight() );
	}


	public void BSTTraverse() {
		if ( this.root != null ) {
			this.getLeftTree().BSTTraverse();
			System.out.print( this.root.getValue() );
			System.out.print( "->" );
			this.getRightTree().BSTTraverse();
		}
	}


	public void BSTInsert( TreeNode n ) {
		TreeNode x = this.root;
		TreeNode y = null;
		while ( x!= null ) {
			y = x;
			if ( n.getValue() < x.getValue() )
				x = x.getLeft();
			else x = x.getRight();
		}
		n.setParent( y );
		if ( y == null )
			this.root = n;	
		else if ( n.getValue() < y.getValue() )
			y.setLeft( n );
		else y.setRight( n );
	}


	public TreeNode TreeMinimum() {
		TreeNode x = this.root;
		while ( x.getLeft() != null )
			x = x.getLeft();
		return x;
	}


	public TreeNode TreeMaximum() {
		TreeNode x = this.root;
		while ( x.getRight() != null )
			x = x.getRight();
		return x;
	}


	//recursive TreeSearch method
	/*public TreeNode TreeSearch( int val ) {


		if ( this.root == null || val == this.root.getValue() )
			return this.root;
		if ( val < this.root.getValue() )
			return this.getLeftTree().TreeSearch( val );
		else return this.getRightTree().TreeSearch( val );
	}*/


	//iterative TreeSearch method
	public TreeNode TreeSearch( int val ) {
		TreeNode x = this.root;
		while ( x != null && val != x.getValue() ) {
			if ( val < x.getValue() )
				x = x.getLeft();
			else x = x.getRight();
		}
		return x;
	}


	public void TransPlant( TreeNode u, TreeNode v ) {


		if ( u.getParent() == null )
			this.root = v;
		else if ( u == u.getParent().getLeft() )
			u.getParent().setLeft( v );
		else u.getParent().setRight( v );
		if ( v != null )
			v.setParent( u.getParent() );


	}


	public void TreeDelete( TreeNode z ) {


		if ( z.getLeft() == null )
			this.TransPlant( z, z.getRight() );
		else if ( z.getRight() == null )
			this.TransPlant( z, z.getLeft() );
		else {
			TreeNode y = ( new BinarySearchTree( z.getRight() ) ).TreeMinimum();


			if ( y.getParent() != z ) {
				this.TransPlant( y, y.getRight() );
				y.setRight( z.getRight() );
				y.getRight().setParent( y );
			}


			this.TransPlant( z, y );
			y.setLeft( z.getLeft() );
			y.getLeft().setParent( y );
		}
	}


	public int Height( BinarySearchTree t ) {
		if ( t.root == null )
			return 0;
		else return ( Math.max( Height( t.getLeftTree() ), Height( t.getRightTree() ) ) + 1 );
	}


	public boolean isBalanced() {
		if ( this.root == null )
			return true;


		if ( Math.abs( Height( this.getLeftTree() ) - Height( this.getRightTree() ) ) > 1 )
			return false;
		else return ( this.getLeftTree().isBalanced() && this.getRightTree().isBalanced() );


	}


}

gistfile3.java

public class TreeNode {


  private int value;
	private TreeNode parent;
	private TreeNode left;
	private TreeNode right;


	public TreeNode( int val ) {
		this.value = val;
		this.parent = null;
		this.left = null;
		this.right = null;
	}


	public int getValue() {
		return value;
	}


	public void setValue( int val ) {
		this.value = val;
	}


	public TreeNode getParent() {
		return this.parent;
	}


	public TreeNode getLeft() {
		return this.left;
	}


	public TreeNode getRight() {
		return this.right;
	}


	public void setParent( TreeNode n ) {
		this.parent = n;
	}


	public void setLeft( TreeNode n ) {
		this.left = n;
	}


	public void setRight( TreeNode n ) {
		this.right = n;
	}


}