public class IntNode {
    private int data;
    private IntNode left;
    private IntNode right;

    public IntNode(int data) {
	this.data = data;
    }
    
    public int getData() {
	return data;
    }

    public IntNode getLeft() {
	return left;
    }

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

    public IntNode getRight() {
	return right;
    }

    public void setLeft(IntNode theleft) {
	left = theleft;
    }

    public void setRight(IntNode theright) {
	right = theright;
    } 

    // recursive in-order traversal
    public void inorder() {
	if (left != null) left.inorder();
	System.out.println(data);
	if (right != null) right.inorder();
    }

    public int countNodes() {
	int leftCount = 0, rightCount = 0;
	if (left != null) leftCount = left.countNodes();
	if (right != null) rightCount = right.countNodes();
	return 1 + leftCount + rightCount;
    }
}

    public class IntBST {
    private IntNode root;

    // constructor
    public IntBST() {
        // do nothing
    }



    public boolean isEmpty() {
        return (root == null);
    }

    // returns the address of the IntNode containing n
    // if there is no such node, returns null
    // Author: Nate Fortuna
    public IntNode search (int n) {
        IntNode node = root;
        while(node != null && node.getData() != n){
            if (n > node.getData()){
                node = node.getRight();
            }else{
                node = node.getLeft();
            }
        }
        return node;
    }

    // inserts n into the Binary Search Tree
    // returns the address of the new IntNode containing n
    // if there already is such a node, the method doesn't 
    // create a new node and returns null
    // Author: Rob Jansen
    public IntNode insert (int n) {
    IntNode node = root;

    while(true)
    {
        if(node == null)
        {
            root = new IntNode(n);
            return root;
        }
        else if(n > node.getData())
        {
            if(node.getRight() == null)
            {
                node.setRight(new IntNode(n));
                return node.getRight();
            }
            else
            {
                node = node.getRight();
            }
        }
        else if(n < node.getData())
        {
            if(node.getLeft() == null)
            {
                node.setLeft(new IntNode(n));
                return node.getLeft();
            }
            else
            {
                node = node.getLeft();
            }
        }
        else
        {
            return null;
        }
    }
        //return null;
    }

    public void inorder() {
	if (root != null) root.inorder();
    }

    public int countNodes() {
	if (root != null) return root.countNodes();
	return 0;
    }


}

public class TestIntBST {
    public static void main(String [] args) {
        IntBST bst = new IntBST();

        bst.insert(6);
        bst.insert(2);
        bst.insert(8);
        bst.insert(5);
        bst.insert(3);
        bst.insert(10);
        System.out.println(bst.insert(5));

        for (int i = 1; i <= 10; ++i) {
            IntNode node = bst.search(i);
            if (node != null) {
                System.out.println(node.getData());
            }
        }

	bst.inOrder();
	System.out.println(bst.countNodes());
    }
}