gistfile1.txt

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() );


	}


}

gistfile2.txt

public class BSTTest {


        public static void main( String[] args ) {


		BinarySearchTree t = new BinarySearchTree();


		t.BSTInsert( new TreeNode( 50 ) );
		t.BSTInsert( new TreeNode( 17 ) );
		t.BSTInsert( new TreeNode( 12 ) );
		t.BSTInsert( new TreeNode( 23 ) );
		t.BSTInsert( new TreeNode( 19 ) );
		t.BSTInsert( new TreeNode( 14 ) );
		t.BSTInsert( new TreeNode( 9 ) );
		t.BSTInsert( new TreeNode( 72 ) );
		t.BSTInsert( new TreeNode( 54 ) );
		t.BSTInsert( new TreeNode( 67 ) );
		t.BSTInsert( new TreeNode( 76 ) );
		t.BSTTraverse();
		System.out.println();
		t.TreeDelete( t.TreeSearch( 50 ) );
		t.BSTTraverse();
		System.out.println();


		if ( t.isBalanced() )
			System.out.println( "This tree is balanced." );
		else System.out.println( "This tree is not balanced." );


	}


}

gistfile3.txt

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

}