public class IntNode {
    private IntNode left, right;
    private int data;
    
    public IntNode(int d){
	data = d;
    }
    
    public IntNode getLeft(){
	return left;
    }
    
    public IntNode getRight(){
	return right;
    }
    public void setLeft(IntNode in){
	left = in;
    }
    public void setRight(IntNode in){
	right = in;
    }
    
    public int getData() {
	return data;
    }

    public void setData(int data) {
        this.data = data;
    }

}

public class IntBST {
    private IntNode root;
    
    public IntBST() {
    }
    
    public boolean isEmpty() {
	return (root == null);
    }
    
    public IntNode getRoot(){
	return root;
    }
    
    // return the reference to the IntNode containing data
    // null if there is no such node
    // This is the search method written by Steve and, independently,
    // by Kyle and Eugene
    public IntNode search(int data ) {
        IntNode node = root;

        while (node != null && data != node.getData()){
            if (data > node.getData()){
                node = node.getRight();
            } else {
                node = node.getLeft();
            }
        }
        return node;
    }
    
    // insert the data into the binary serach tree
    // return the reference to the new node containing data
    // if there already is such a node, return null
    public IntNode insert(int data) {
        if(!isEmpty()){
            IntNode parent = getRoot();
            IntNode child;
            if (data == parent.getData()) {
                return null;
            }
            if(data < parent.getData()){
                child = parent.getLeft();
            } else {
                child = parent.getRight();
            }
       
            while(child != null){
                if(data < child.getData()){
                    parent = child;
                    child = child.getLeft();
                } 
                else if (data > child.getData()) {
                    parent = child;
                    child = child.getRight();
                }
                else return null;
            }
            IntNode node = new IntNode(data);
            if(parent.getData() < data){
                parent.setRight(node);
            }
            else{
                parent.setLeft(node);    
            }
            return node;
        }
	// if the tree is empty
        IntNode node = new IntNode(data);
        root = node;
        return node;
    }
	
}