Inorder successor in Binary Search Tree (BST)

This is a very common topic and needs to be understood first theoretically.

Inorder traversal in a binary search tree consist of 3 steps when we give a node as input to in-order program/function:-

(1) visit left node of the parent input node. (Print it).
(2) visit the parent input node. (Print it).
(3) visit right node of the parent input node. (Print it).

We need to repeat the above steps recursively. We can refer the above image to visualize how the in-order traversal will work in BST.

Lets come back to our main point of discussion which is to find the in-order successor in a BST.

Point to note :- When we try to find in-order successor of a node-in-question, in that case basically we try to find the smallest node (but greater than  node-in-question) connected to node-in-question.

In-order successor basically do the same. It gives us the smallest node among all the nodes (greater than node-in-question), connected to the node-in-question. Refer the above image, in-order successor of 6 is 8...in-order successor of 8 is 10 etc...

Now we can basically face 3 scenarios while trying to find the in-order successor for binary search.

Case 1:- Node has right subtree

If we want to find the in-order successor of 10, then we will go in the right subtree and find the smallest node which will be left most node. Successor of 10 is 11

Case 2:- Node has no right subtree

Scenario1

If we want to find in-order successor of 8, then because there is no subtree for 8, so according to in-order traversal rule, after visit 8, logic will go to its parent 10 in the absence of right subtree. In-order successor of 8 will be 10.

Scenarion2

If we want to find the in-order successor of node 12, then since it has no right subtree, it will move back to its parent which is node 10. Since the parent would have also been visited according to in-order traversal also, we will further go up to nodes grandparent node which in this case is node 15 which wouldn't have been visited. So successor of 12 will be 15.

private Node getSuccessor(Node delNode)

{

Node successorParent = delNode;

Node successor = delNode;

Node current = delNode.rightChild; // go to right child

while(current != null) // until no more

{ // left children,

successorParent = successor;

successor = current;

current = current.leftChild; // go to left child

}

// if successor not

if(successor != delNode.rightChild) // right child,

{ // make connections

successorParent.leftChild = successor.rightChild;

successor.rightChild = delNode.rightChild;

}

return successor;

}

In the above program we do not take into consideration the successor from Case 2 Scenario 2