/** ein binaerer Suchbaum mit ganzen Zahlen als Datensatz */
public class BinarySearchTree {

	/** die Knotenklasse als statische innere Klasse */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int value) {
			this.value = value;
		}
	}

	private TreeNode root;

	/**
	 * Herausfinden, ob ein gewisser Datensatz schon im binaeren Suchbaum enthalten ist.
	 *
	 * @param   data  zu suchender Datensatz
	 * @return        true: Datensatz ist vorhanden; false: Datensatz ist nicht vorhanden.
	 */
	public boolean contains(int data) {
		TreeNode temp = root;
		while(temp != null) {
			if (temp.value == data) {
				return true;
			}
			if (temp.value > data) {
				temp = temp.left;
			} else {
				temp = temp.right;
			}
		}
		return false;
	}

	/**
	 * Einen neuen Datensatz in den binaeren Suchbaum einfuegen.
	 *
	 * @param   data  einzufuegender Datensatz
	 * @return        true: Datensatz wurde eingefuegt; false: Datensatz war schon vorhanden.
	 */
	public boolean insert(int data) {
		if (root == null) {
			root = new TreeNode(data);
			return true;
		}
		
		TreeNode temp = root;
		while(temp.value != data) {
			if (temp.value > data) {
				if(temp.left == null) {
					temp.left = new TreeNode(data);
					return true;
				}
				temp = temp.left;
			} else {
				if (temp.right == null) {
					temp.right = new TreeNode(data);
					return true;
				}
				temp = temp.right;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		BinarySearchTree tree = new BinarySearchTree();
		for (int i = 0; i < 20; i++) {
			int x = (int) (Math.random() * 50);
			System.out.println(x);
			tree.insert(x);
		}
		for (int i = 0; i < 50; i++) {
			System.out.println(i + ": " + tree.contains(i));
		}
	}
}