Binary Search Tree Operations [Find, Insert, Delete, Print][Using Father Node Field][BST][Java Implementation]

Previous post on BST did not use Father field. This program uses Father field in Node.

Source:

import java.util.Scanner;

public class BSTFather {

    Node root;

    class Node {

        Node father, left, right;
        int key;

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

        public String toString() {
            return Integer.toString(key);
        }
    }

    public void insert(Node toInsert, Node node) {
        if (root == null) {
            root = toInsert;
            return;
        }

        if (toInsert.key < node.key) {
            if (node.left != null) {
                insert(toInsert, node.left);
            } else { 
                toInsert.father = node;
                node.left = toInsert;
            }
        } else if (toInsert.key >= node.key) {
            if (node.right != null) {
                insert(toInsert, node.right);
            } else { 
                toInsert.father = node;
                node.right = toInsert;
            }
        }
    }

    public Node findNode(Node findNode, Node node) {
        if (root == null) {
            return null;
        }

        if (findNode.key < node.key) {
            if (node.left != null) {
                return findNode(findNode, node.left);
            } 
        } else if (findNode.key > node.key) {
            if (node.right != null) {
                return findNode(findNode, node.right);
            } 
        } else if (findNode.key == node.key) {
            return node;
        }
        return null;
    }

    public boolean deleteNode(Node deleteNode, Node node) {
        if (root == null) return false;
        else if (root.key == deleteNode.key) {
            if(root.left == null && root.right == null) root = null;
            else if (root.left == null) { root = root.right; root.father = null; }
            else if (root.right == null) { root = root.left; root.father = null; }
            else {
                Node min = root.right;
                //min element has no left or right child.
                if(min.left==null && min.right==null){
                    root.key = min.key;
                    root.right = null; 
                    return true;
                } 
                while(min.left!=null){
                    //Min element has left child.
                    min = min.left;
                }
                root.key = min.key; 
                if(min.right!=null) min.right.father = min.father;
                //Min element has no left child but has right child.
                if(min.father!=root) min.father.left = min.right;
                else{ min.father.right = min.right;} 
            }
            return true;
        }
        else { 
            Node locatedNode = findNode(deleteNode, root); 
            if(locatedNode!=null) deleteHelper(locatedNode);
            else return false;
        }
        return true;
    }

    private void deleteHelper(Node locatedNode) {
        boolean left = (locatedNode.father.left == locatedNode); 
        if(locatedNode.right == null && locatedNode.left == null){
            if(left) locatedNode.father.left = null;
            else locatedNode.father.right = null;
        }
        else if(locatedNode.left!=null && locatedNode.right == null){ 
            locatedNode.left.father = locatedNode.father;
            if(left) locatedNode.father.left = locatedNode.left;
            else locatedNode.father.right = locatedNode.left;
        }else if(locatedNode.left==null && locatedNode.right!=null){
            locatedNode.right.father = locatedNode.father;
            if(left) locatedNode.father.left = locatedNode.right;
            else locatedNode.father.right = locatedNode.right;
        }else if(locatedNode.left!=null && locatedNode.right!=null){ 
            Node min = locatedNode.right;
            //min element has no left or right child.
            if(min.left==null && min.right==null){
                locatedNode.key = min.key;
                locatedNode.right = null;
                return;
            } 
            while(min.left!=null){
                //Min element has left child.
                min = min.left;
            }
            locatedNode.key = min.key; 
            if(min.right!=null) min.right.father = min.father;
            //Min element has no left child but has right child.
            if(min.father!=locatedNode) min.father.left = min.right;
            else{ min.father.right = min.right;} 
            
        }
    }

    public void deleteTree(){
        root = null;
    }
    
    public void printTree(Node node) {
        if (node == null) {
            return;
        }
        printTree(node.left);
        System.out.print(node.key+" ");
        printTree(node.right);
    }

    public void consoleUI(){
        Scanner scan = new Scanner(System.in);  
        while (true) {
            System.out.println("\n1.- Add items\n"
                    + "2.- Delete items\n"
                    + "3.- Check items\n"
                    + "4.- Print tree\n"
                    + "5.- Delete tree\n");
            int choice = scan.nextInt();

            int item;
            Node node;
            switch (choice) {
                case 1:
                    item = scan.nextInt(); 
                    while (item != -999) {
                        node = new Node(item, null, null, null);
                        insert(node, root);
                        item = scan.nextInt(); 
                    }
                    printTree(root);
                    break;
                case 2:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item, null, null, null);
                        System.out.print("\nDeleting item "+item); 
                        if(deleteNode(node, root)){
                            System.out.print(": deleted!"); 
                        }else
                            System.out.print(": does not exist!"); 
                        item = scan.nextInt();
                    }
                    System.out.println();
                    printTree(root);
                    break;
                case 3:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item, null, null, null);
                        System.out.println((findNode(node, root)!=null)?"found":"not found");
                        item = scan.nextInt();
                    }
                    break;
                case 4:
                    printTree(root);
                    break;
                case 5:
                    deleteTree();
                    System.out.println("Tree deleted!");
                    break;
            }
        }
    }
    
    public static void main(String[] args) {
        BSTFather bst = new BSTFather();   
        bst.consoleUI();
        
    }
}

Output:

1.- Add items

2.- Delete items

3.- Check items

4.- Print tree

5.- Delete tree

1

1 2 77 5 4 99 7 4 6 -999

1 2 4 4 5 6 7 77 99 

1.- Add items

2.- Delete items

3.- Check items

4.- Print tree

5.- Delete tree

2

4 5 7 4 6 77 99 1 2 -999

Deleting item 4: deleted!

Deleting item 5: deleted!

Deleting item 7: deleted!

Deleting item 4: deleted!

Deleting item 6: deleted!

Deleting item 77: deleted!

Deleting item 99: deleted!

Deleting item 1: deleted!

Deleting item 2: deleted!

As expected!