// BinaryTree.java
import java.util.Scanner;
public class BinaryTree
{
  private static class Node
  {
    private Node left;
    private Node right;
    private int data;

  	public Node(int newData)
    {
      left = null;
      right = null;
      data = newData;
    }
  }

	private Node root;

  public void BinaryTree()
  {
    root = null;
  }

  public boolean lookup(int data)
  {
    return(lookup(root, data));
  }

  private boolean lookup(Node node, int data)
  {
    if (node==null)
      return(false);
    if (data==node.data)
      return(true);
    else if (data<node.data)
      return(lookup(node.left, data));
    else
      return(lookup(node.right, data));
  }

 	public void insert(int data)
 	{
    root = insert(root, data);
  }

  private Node insert(Node node, int data)
  {
    if (node==null)
      node = new Node(data);
    else
    {
      if (data <= node.data)
        node.left = insert(node.left, data);
      else
        node.right = insert(node.right, data);
    }
    return(node);
	}

	public void print()
	{
		print(root);
	}

	private void print(Node node)
	{
		if(node != null)
		{
			print(node.left);
			System.out.print(node.data + " ");
			print(node.right);
		}
	}
  public static void main(String[] args)
  {		// 12 7 15 89 17
    		BinaryTree bt = new BinaryTree();
    		// insert all ..
    		bt.insert(12);
    		bt.insert(7);
    		bt.insert(15);
    		bt.insert(89);
    		bt.insert(17);

    		bt.print();
    		// try to find if num (from the keyboard) is there
    		//	output the message
    		Scanner input = new Scanner(System.in);
    		System.out.print("\n\nInput the item to look up from tree: ");
    		int num = input.nextInt();
    		if(bt.lookup(num))
    			System.out.println(num + " is in the tree!.\n\n");
    		else
    			System.out.println(num + " is NOT in the tree!.\n\n");

    		System.out.println("Bye.\n\n");
    }
 }