public class BinarySearchTree {

    public static class Node {
        int key;
        Node left;
        Node right;

        public Node (int key) {
            this(key, null, null);
        }

        public Node (int key, Node left, Node right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }
    }

    public static class BST {
        Node parent;
        int count;

        public BST(int parent) {
            this.parent = new Node(parent);
        }

        public void insert(int key) {
            insert(parent, key);
            count += 1;
        }

        public void insert(Node node, int key) {
            if (key > node.key) {
                if (node.right == null) {
                    node.right = new Node(key);
                } else {
                    insert(node.right, key);
                }
            }
            if (key < node.key) {
                if (node.left == null) {
                    node.left = new Node(key);
                } else {
                    insert(node.left, key);
                }
            }
        }

        public boolean exists(int key) {
            return exists(key, parent);
        }

        public boolean exists(int key, Node n) {
            if (n == null) {
                return false;
            }
            if (n.key == key) {
                return true;
            }
            return exists(key, n.left) || exists(key, n.right);
        }

        public void printTree() {
            printTree(parent, 0, 0);
        }

        public void printTree(Node n, int depth, int type) {
            if (n == null) {
                return;
            }
            for(int i = 0; i < depth; i++) {
                System.out.print("\t");
            }
            if(type == 0) {
                System.out.print("Parent: ");
            }
            if(type == 1) {
                System.out.print("Left: ");
            }
            if(type == 2) {
                System.out.print("Right: ");
            }
            System.out.print(n.key + "\n");
            printTree(n.left, depth + 1, 1);
            printTree(n.right, depth + 1, 2);
        }

    }

    public static void main(String[] args) {
        BST tree = new BST(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
        tree.printTree();
        System.out.println(tree.exists(40));
        System.out.println(tree.exists(69));
    }

}