Find Successor of a Node
A Node successor is the next larger value in the tree. As we know that the left side of the tree will contain smaller value than the Node therefore we will have to look somewhere to the right side. There are two case here:

If Node has right child

If a node has a right child, then the successor is the minimum of that. First go to the right child and then go to the last left of that right child. If there is no left child of the right then the right child itself will be the successor. For example consider below tree –

The successor of Node 6 will be Node 7.
The successor of Node 4 will be Node 5.

If Node doesn’t have right child

If a node right child is null, the to find the successor you will have go to up in the tree until you find the value greater than the node value. For example in above tree –

The successor of Node 5 will be Node 6.
The successor of Node 7 will be Node 9.
The successor of Node 2 will be Node 4.
The successor of Node 9 will be null since it is the maximum.

Please note that there is no successor for the maximum node.

Java implementation to find the Successor in Binary search tree.

 public Node getSuccessor(Node node){
        if (node == null){
            return null;
        }
        Node successor = null;
        Node currentNode = node.right;
        if (currentNode != null) {
            while (currentNode != null) {
                successor = currentNode;
                currentNode = currentNode.left;
            }
        }else{
            currentNode = node.parent;
            while(currentNode != null && currentNode.value < node.value){
                currentNode = currentNode.parent;
            }
            successor = currentNode;
        }
        return successor;
    }

Find Predecessor of a Node
A Node predecessor is the next smaller value in the tree.This is just the reverse of Successor. As we know that the left side of the tree will contain smaller value than the Node therefore we will have to look somewhere to the left side. Here also there are two case here as above:

If Node has left child

If a node has a left child, then the predecessor is the maximum of that. First go to the left child and then go to the last right of that left child. If there is no right child of the left then the left child itself will be the predecessor. For example consider below tree –

The predecessor of Node 6 will be Node 5.
The predecessor of Node 4 will be Node 2.
The predecessor of Node 9 will be Node 7.

If Node doesn’t have left child

If a node left child is null, the to find the predecessor you will have to go up in the tree until you find the value lesser than the node value. For example in above tree –

The predecessor of Node 5 will be Node 4.
The predecessor of Node 7 will be Node 6.
The predecessor of Node 2 will be null since it is the minimum.

Please note that there is no predecessor for the minimum node.

Java implementation to find the predecessor in Binary search tree.

 public Node getPredecessor(Node node){
        if (node == null){
            return null;
        }
        Node predecessor = null;
        Node currentNode = node.left;
        if (currentNode != null) {
            while (currentNode != null) {
                predecessor = currentNode;
                currentNode = currentNode.right;
            }
        }else{
            currentNode = node.parent;
            while(currentNode != null && currentNode.value > node.value){
                currentNode = currentNode.parent;
            }
            predecessor = currentNode;
        }
        return predecessor;
    }

Go to the next page – Click on the below red circle with page number.