Binary Search Trees - Insert, Find, Delete, Print Tree Operations [Java]

This program implements Insert, Find, Delete Node and Print operations on a Binary Search Tree. The inorder traversal of a Binary Search Tree yields the elements in ascending order.

This program doesn't use Father field in Node class. Here is another program that has Father field in nodes : Using Father Field BST

Code:

import java.util.Scanner;

public class BinarySearchTree {

    private class Node {

        int key;
        Node left, right;

        Node(int key) {
            this.key = key;
        }
    }

    private Node root;

    /* Adds an item to the BST */
    public void add(int a) {
        if (root == null) { root = new Node(a); } 
        else              { adder(a, root, null, false); }
    }

    private void adder(int a, Node node, Node parent, boolean isLeft) {

        if (node == null) {
            if (isLeft) { parent.left = new Node(a); } 
            else        { parent.right = new Node(a); }
            return;
        }

        if (a >= node.key) { adder(a, node.right, node, false); } 
        else               { adder(a, node.left, node, true); }
    }

    /* Checks whether an item is in the tree */
    public boolean isNode(int a) {
        if(root == null) return false;
        return nodeFinder(a, root);
    }

    private boolean nodeFinder(int a, Node node) {
        if (node.key == a) { return true; }

        if (a >= node.key) { return nodeFinder(a, node.right); } 
        else               { return nodeFinder(a, node.left); }
    }

    /* Deletes a node from the tree */
    public boolean delete(int a) {
        if (root == null) { return false; }
        
        //Target element is the root and either left or right subtree is empty
        if(root.key == a){
            if (root.left == null && root.right == null) 
                { root = null; return true;}
            else if(root.right == null)    //Root with only left subtree 
                { root = root.left; return true;}
            else if(root.left == null)                    //Root with right subtree only
                { root = root.right; return true;} 
        }
        return deleter(a, root, null); 
    }

    private boolean deleter(int a, Node node, Node parent) {  
        
        //Node is not present. Return false. 
        if(node == null){ return false; }
        

        //Node to be deleted is either a leaf or has only one child 
if (node.left != null && node.left.key == a) {
            if (node.left.left == null) { 
                node.left = node.left.right; 
                return true;
            } else if (node.left.right == null) { 
                node.left = node.left.left; 
                return true;
            } 
        } else if (node.right != null && node.right.key == a) {
            if (node.right.left == null) { 
                node.right = node.right.right;
                return true;
            } else if (node.right.right == null) { 
                node.right = node.right.left;
                return true;
            }
        }

        //Node to be deleted has two children
        if (node.key == a) { 
            Node smallestNodesParent = smallestNodesParent(node.right);

            if (smallestNodesParent.left != null) { 
                node.key = smallestNodesParent.left.key;
                smallestNodesParent.left = smallestNodesParent.left.right;
            } else {
                node.key = smallestNodesParent.key;
                node.right = smallestNodesParent.right;
            }
            return true;
        }

        //Go left or right?
        if (a > node.key)     { return deleter(a, node.right, node); } 
        else if(a < node.key) { return deleter(a, node.left, node);  }  
        
        //Never gets Returned - One of the three conditions - equal, less or greater
        //return before reaching here.
        return false;
    }

    /* 
       returns the smallest nodes parent node, or if the node first passed to 
       this function has no left child, it just returns the node passed to it
    */
    private Node smallestNodesParent(Node node) {
        if (node.left != null) {
            if (node.left.left == null) {
                return node;
            }
        } else {
            return node;
        }

        return smallestNodesParent(node.left);
    }

    /* 
       Prints the tree contents - Inorder traversal - 
       Inorder traversal of a BST yields the items in
       ascending order
    */
    public void printTree() {
        print(root);
    }

    private void print(Node node) {
        if (node == null) {
            if (root == null) {
                System.out.println("Tree is empty!");
            }
            return;
        }
        print(node.left);
        System.out.print(node.key + " ");
        print(node.right);
    }
    
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Scanner scan = new Scanner(System.in);
        
        //Display a Console Interface
        while (true) {
            System.out.println("\n1.- Add items\n"
                    + "2.- Delete items\n"
                    + "3.- Check items\n"
                    + "4.- Print tree\n");
            int choice = scan.nextInt();

            int item;

            switch (choice) {
                case 1:
                    item = scan.nextInt();
                    while (item != -999) {
                        bst.add(item);
                        item = scan.nextInt();
                    }
                    bst.printTree();
                    break;
                case 2:
                    item = scan.nextInt();
                    while (item != -999) {
                        System.out.print("\nDeleting item "+item); 
                        if(bst.delete(item)){
                            System.out.print(": deleted!"); 
                        }else
                            System.out.print(": does not exist!"); 
                        item = scan.nextInt();
                    }
                    System.out.println();
                    bst.printTree();
                    break;
                case 3:
                    item = scan.nextInt();
                    while (item != -999) {
                        System.out.println(bst.isNode(item));
                        item = scan.nextInt();
                    }
                    break;
                case 4:
                    bst.printTree();
                    break;
            }
        }
    }
}

Output: 

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

1
9 3 14 2 8 12 14 13 112 19 -999
2 3 8 9 12 13 14 14 19 112
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

2
3 14 14 13 112 -999

Deleting item 3: deleted!
Deleting item 14: deleted!
Deleting item 14: deleted!
Deleting item 13: deleted!
Deleting item 112: deleted!
2 8 9 12 19
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

2
8 9 12 19 2 -999

Deleting item 8: deleted!
Deleting item 9: deleted!
Deleting item 12: deleted!
Deleting item 19: deleted!
Deleting item 2: deleted!
Tree is empty!

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree