Find InOrder successor of a node in binary search tree using java (example)

• Given a binary search tree (bst), find inorder successor using iterative algorithm.
• What is InOrder successor in BST?
  • The smallest key, greater than input node in binary search tree (BST).
• We have discussed similar problem find inorder predecessor in binary search tree.

The inorder traversal (DFS) of binary search tree is :
25 50 75 100 120 125 140 150 160 175 190
InOrder traversal of binary search tree, gives the sorted output. So, inorder successor is next higher number of input number.

Examples to find successor of input node:

Let us analyse above InOrder successors with the help of examples:

Example 1: InOrder successor of Node H (120)?

• Node H is left child of node F.
  • The parent node of F will be next higher next.(Property of BST.)
• Node F will be InOrder successor of Node H.

Example 2: InOrder successor of  Node E (75) ?

• Node E does not have any children.
  • InOrder successor will be lying somewhere in parents nodes (similar to case example 1).
• We can see that its successor is Node A

How many parents nodes we need to traverse to find the successors?
In example 1, we had travel just one parent. By keeping in mind the properties of binary search tree, we need the first parent, from where current node, is lying on the left side of it. Let us traverse the tree to understand it better.

• We are looking for ancestor of Node E.
• Go to parent to Node E, which is Node B.
  • Is Node E  lying on the left side of Node B ?
    • No, Go to parent of Node B i.e. Node A.
      • Node E is lying left side of Node A ?
        • Yes, Node A is InOrder successor of Node E.

Arise of First Condition to find Inorder Successor:
If a node do not have any right child then we will to traverse to parent nodes to find inorder successor of binary tree.

Example 3: InOrder successor of 125 (Node F) ?

• Node F has right child.
  • Property of BST, the right child of binary tree is greater than its parent node
• Node I will Inorder Successor node.
• As shown in Fig 4, If a node has ONLY one right child, then right child will be Inorder successor.

Example 4: InOrder successor of 150 (Node C) ?

• Node C has right subtree (children).
  • Inorder successor (next bigger number) is lying on right sub tree
• Smallest possible number in right sub tree, will be Inorder successor
• Node J is smallest element in the right sub tree of Node C.
• Node J is Inorder successor of Node C

Arise of Second (and last) Condition to find Inorder Successor
Example 3 and example 4 will be our second or last condition to find the inorder successor of binary search tree.
Conclusion to find InOrder Successor in BST: We can categorize the algorithm into following categories

• InOrder Successor of node, Who not have any right children (Example 1 & Example 2)
• InOrder Successor of node, Who have any right children (Example 3 & Example 4)

Algorithm: find Inorder successor in a BST using java

• We would like to find inorder successor of node.
• Check node have right child (Example 3 & example 4)
  • If node have right subtree, Inorder successor is in right subtree.
    • Find out InOrder successor in right subtree
      • Return the inorder successor
  • If right child is null, InOrder is lying somewhere in parents
    • Example 1 and Example 2
    • Go to parents and search InOrder successor.
• Find InOrder successor in parent nodes.
• Start traversing the binary search tree from root.
• Search inorder successor in parent nodes (of input node)
  • So, equality of root data with input node, will be our exit condition
    • We would have found the node before arriving this condition.
• If we encounter left child ( keep on scanning the BST)
  • Save it as inorder successor
  • We are interested in left child ONLY.
    • As discussed in example 1 and example 2
• If we encounter right child, Keep traversing the binary tree.
• At end of traversal, we will have inorder successor.

Program – find InOrder successor of given node in a BST using java

1.) InorderSuccessor class:

• Traverse binary search tree using iterative method.
• successor will give inorder successor of input node in BST

package org.learn.Question;
import org.learn.PrepareTree.Node;

public class InorderSuccessor {
	private static Node min(Node root) {
		//we found the min node
		if(root.left == null) {
			return root;
		}
		return min(root.left);
	}
	
	public static Node successor(Node root, Node node) {
		//Example 3 or Example 4
		if(node.right != null)
			return min(node.right);
		
		//Example 1 or Example 2
		Node successor = null;
	    // Start from root and search for successor down the tree
	    while (root != null)
	    {
	    	if(node.data == root.data) {
	    		//by now we might found our successor
	    		break;
	    	} else if (node.data < root.data) {
	        	successor = root;
	            root = root.left;
	        } else if (node.data > root.data)
	            root = root.right;	       
	    }
	   return successor;
	}
}

2.) Node class:

• Node class representing the node (s) of a binary search tree.

package org.learn.PrepareTree;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App class:

• We are constructing binary search tree in main method.
• We are calling the method of InorderSuccessor class, to find inorder successor of a given node.

package org.learn.Client;

import org.learn.PrepareTree.Node;
import org.learn.Question.InorderSuccessor;

public class App 
{
    public static void main( String[] args )
    {  
       //root level 0
       Node A = Node.createNode(100);
       //Level 1
       Node B = Node.createNode(50);
       Node C = Node.createNode(150);
       //Level 2
       Node D = Node.createNode(25);
       Node E = Node.createNode(75);
       Node F = Node.createNode(125);
       Node G = Node.createNode(175);
       //Level 3
       Node H = Node.createNode(120);
       Node I = Node.createNode(140);
       Node J = Node.createNode(160);
       Node K = Node.createNode(190);
             
       //connect Level 0 and 1
       A.left = B;
       A.right = C;
       //connect level 1 and level 2
       B.left = D;
       B.right = E;
       C.left = F;
       C.right = G;
       //Connect level 2 and level 3
       F.left = H;
       F.right = I;
       G.left = J;
       G.right = K;
         
       Node successor = InorderSuccessor.successor(A, H);
       System.out.printf("Inorder successor of Node %d is %d\n",H.data, successor.data);     
       
       successor = InorderSuccessor.successor(A, E);
       System.out.printf("Inorder successor of Node %d is %d\n",E.data, successor.data);     
       
       successor = InorderSuccessor.successor(A, F);
       System.out.printf("Inorder successor of Node %d is %d\n",F.data, successor.data);     
       
       successor = InorderSuccessor.successor(A, C);
       System.out.printf("Inorder successor of Node %d is %d\n",C.data, successor.data); 
       
       successor = InorderSuccessor.successor(A, A);
       System.out.printf("Inorder successor of Node %d is %d\n",A.data, successor.data);  
    }
}

Output – InOrder successors of a given node using java

InOrder successor of Node 120 is 125
InOrder successor of Node 75 is 100
InOrder successor of Node 125 is 140
InOrder successor of Node 150 is 160
InOrder successor of Node 100 is 120<

Download code – find InOrder Successor in BST using java