BinarySearchTree.java

public class BinarySearchTree {
    public static void main(String args[]){
        System.out.println("*******************Binary Search Tree******************");
        Node tree = insert(5, null);
        insert(3, tree);
        insert(2, tree);
        insert(4, tree);
        insert(7, tree);
        insert(6, tree);
        insert(8, tree);
        System.out.println("*******************Inorder Binary Tree Transversal******************");
        inorderTransversal(tree);
        System.out.println("*******************Preorder Binary Tree Transversal******************");
        preorderTransversal(tree);
        System.out.println("*******************Postorder Binary Tree Transversal******************");
        postorderTransversal(tree);
        System.out.println("*******************Searching in Binary Tree ******************");
        searchBST(6, tree);
        searchBST(11, tree);
    }

    /**
     * @param node
     * @param key
     */
    private static void searchBST(int key, Node node) {
        if(node == null)
            System.out.println("Key not found in the tree");
        else if(node.getData().equals(key))
            System.out.println("Key found in the tree");
        else if(key > node.getData())
            searchBST(key, node.getRight());
        else if(key < node.getData())
            searchBST(key, node.getLeft());
    }

    public static Node insert(Integer key, Node node){
        /**
         * Node is null. This means tree doesn't exist yet.
         * So, we will just initialize a node and return
         */
        if(node == null) {
            return new Node(key, null, null);
        }
        if(key > node.getData())
            node.setRight(insert(key, node.getRight()));
        if(key < node.getData())
            node.setLeft(insert(key, node.getLeft()));
        return node;
    }

    /**
     * Inorder Transversal prints in a sorted order.
     * Prints root in between the left and right children
     * @param node
     */
    public static void inorderTransversal(Node node) {
        if(node == null)
            return;
        inorderTransversal(node.getLeft());
        System.out.println(node.getData());
        inorderTransversal(node.getRight());
    }


    /**
     * Prints root before the left and right node
     * @param node
     */
    public static void preorderTransversal(Node node) {
        if(node == null)
            return;
        System.out.println(node.getData());
        preorderTransversal(node.getLeft());
        preorderTransversal(node.getRight());
    }

    /**
     * Prints root after the left and right node
     * @param node
     */
    public static void postorderTransversal(Node node) {
        if(node == null)
            return;
        postorderTransversal(node.getLeft());
        postorderTransversal(node.getRight());
        System.out.println(node.getData());
    }


}