Binary Search Tree implementation java : Insertion, Deletion, Right Rotate, Left Rotate, Predecessor, Successor, Inorder

A binary search tree is a data structure having the following properties

• It has only one root node.
• Each node can have at most two children.
• The value of left child is always smaller than its parent.
• The value of right child is always greater than its parent.
• Every node has the following attributes :- parent, leftChild, rightChild and key.

Inorder Traversal: It is a kind of traversal in which first the nodes of every subtree are processed in the following order : left child, root and right child. In this way the nodes of a tree are processed in an ascending order.

Tree Minimum(x): It returns the node with the minimum value of the subtree rooted at x.

Tree-Successor(x): It returns the node in the tree whose key value is next higher than the key of node x.

Tree-Predecessor(x): It returns the node in the tree whose key value is next lower than the key of node x.

Insertion: To insert a node z in a tree first appropriate position is found for it based on the value of its key. After its positions is found other attributes of the node like:- left, right and parent are update. The parent of the node is also updated.
The insertion algorithm is as follows :

Deletion:
The deletion procedure makes a call to another procedure transplant which replace one node with another. The algorithm for transplant is as follows:

The deletion algorithm can be divided into three cases:
         Case 1: If x has no children.
         Case 2: If x has just one child.
         Case 3: If x has both children.

The deletion algorithm can be best understood via the following flow chart:

Note the following source code and above diagrams have been developed using text from
Introduction to Algorithms, 3rd Edition

public class BST {

    private Node root;

    Node getRoot() {
        return root;
    }

    void setRoot(Node root) {
        this.root = root;
    }

    void insert(Node z) {
        Node y = null;
        Node x = getRoot();
        while (x != null) {
            y = x;
            if (z.getKey() < x.getKey()) {
                x = x.left();
            } else {
                x = x.right();
            }
        }
        z.setParent(y);
        if (y == null) {
            setRoot(z);
        } else if (z.getKey() < y.getKey()) {
            y.setLeft(z);
        } else {
            y.setRight(z);
        }

    }

    void inorder(Node x) {

        if (x != null) {
            inorder(x.left());
            System.out.print(x.getKey() + "\t");
            inorder(x.right());
        }

    }

    void leftRotate(Node x) {
        Node y = x.right();
        if(y==null)
        {
            System.out.println("The tree cannot be left rotated");
            return;
        }
        x.setRight(y.left());//Turn y's left subtree into x's subtree
        if (y.left() != null) {
            y.left().setParent(x);

        }
        y.setParent(x.parent());
        if (x.parent() == null) {
            setRoot(y);
        } else if (x == x.parent().left()) {
            x.parent().setLeft(y);
        } else {
            x.parent().setRight(y);
        }
        y.setLeft(x);
        x.setParent(y);

    }

    void rightRotate(Node x) {
        Node y = x.left();
        if(y==null)
        {
            System.out.println("The tree cannot be right rotated");
            return;
        }
        x.setLeft(y.right());//Turn y's left subtree into x's subtree
        if (y.right() != null) {
            y.right().setParent(x);

        }
        y.setParent(x.parent());
        if (x.parent() == null) {
            setRoot(y);
        } else if (x == x.parent().left()) {
            x.parent().setLeft(y);
        } else {
            x.parent().setRight(y);
        }
        y.setRight(x);
        x.setParent(y);

    }
 

    Node successor(Node x) {
        if (x.right() != null) {
            x = x.right();
            while (x.left() != null) {
                x = x.left();
            }
            return x;
        } else {
            Node y = x.parent();
            while (y != null && x == y.right()) {
                x = y;
                y = y.parent();
            }
            return y;
        }
    }

    Node predecessor(Node x) {
        Node predc = null;
        if (x.left() != null) {
            predc = x.left();
            // System.out.println("Checking-"+predc.getKey());
            while (predc.right() != null) {

                predc = predc.right();

            }

            return predc;
        } else {
            predc = x.parent();
            while (predc != null && x == predc.left()) {
                x = predc;
                predc = predc.parent();
            }

        }
        return predc;

    }

    void transplant(Node u, Node v) {
        if (u.parent() == null) {
            setRoot(v);
        } else if (u == u.parent().left()) {
            u.parent().setLeft(v);
        } else {
            u.parent().setRight(v);
        }
        if (v != null) {
            v.setParent(u.parent());
        }
    }

    void delete(Node x) {
        if (x.left() == null) {
            transplant(x, x.right());
        } else if (x.right() == null) {
            transplant(x, x.left());
        } else {
            Node y = minChild(x.right());
            if (y.parent() != x) {
                transplant(y, y.right());
                y.setRight(x.right());
                y.right().setParent(y);
            }
            transplant(x, y);
            y.setLeft(x.left());
            y.left().setParent(y);
        }
    }

    Node minChild(Node x) {
        while (x.left() != null) {
            x = x.left();
        }
        return x;
    }

}

class Node {

    private Node left, right, parent;
    private int key;

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

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public Node left() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node right() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public Node parent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "Node{" +key+ "}";
    }

}