Inorder Successor in Binary Trees
The next node in the Inorder traversal of a binary tree is known as Inorder successor of that particular node.
In a Binary Search Tree, the definition of Inorder successor can be defined in another way also. It is a node which is the smallest key that is greater than the key of the input node. This is implied because in the Binary Search Tree, the Inorder traversal gives the ascending order of the elements present in the tree.
The above diagram is a Binary Search Tree. So, in the above tree the Inorder successor of 3 is 5. And also the Inorder successor of 3 is 5.
In this way we can find the Inorder successor of a particular node by viewing the structure of the tree. If we know the Inorder traversal of a particular tree also we can find the Inorder successor of a particular node.
Method 1 – Using the Parent Pointer.
An assumption is that every node in the tree has a parent pointer. In this method, an algorithm is designed which is divided into two cases. This is divided based on the right sub tree of the node is empty or not empty.
In this algorithm, the particular node along with its root node is given as the input. And the Inorder successor of the provided node is given as the output.
The algorithm works on the following principles.
- Check if the right sub tree is NULL or not NULL.
If it is not NULL, then the Inorder successor of that node lies in the right sub tree. It is the node in the right sub tree having the minimum key value. - If the right sub tree of that node is NULL, then the Inorder successor lies between one of the ancestors. So, using the parent pointer (which is assumed that every node has a parent pointer) we should travel upwards to find the Inorder successor. We should find a node which is the left child of its corresponding parent. So, the parent node of such node becomes the Inorder successor of the provided node in the input.
Let’s implement this algorithm using JAVA programming language.
// Java program to find the Inorder successor in Binary Search Tree.
// A node for the binary tree is created.
class Node {
int data;
Node left, right, parent;
Node (int d)
{
data = d;
left = right = parent = null;
}
}
class BinaryTreeDemo {
static Node head;
/* Given a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(The standard trick to avoid using reference
parameters). */
Node insert (Node new_node, int data)
{
/* 1. Check if the binary tree is empty. If yes, then return a new
Binary tree with a single node.
*/
if (new_node == null) {
return (new Node (data));
}
else {
Node temp = null;
/* 2. If the tree is not empty, recur down the tree. */
if (data <= new_node.data) {
temp = insert (new_node.left, data);
new_node.left = temp;
temp.parent = new_node;
}
else {
temp = insert (new_node.right, data);
new_node.right = temp;
temp.parent = new_node;
}
/* return the (unchanged) node pointer */
return new_node;
}
}
Node inOrderSuccessor (Node root, Node n)
{
// code for the first step in the above algorithm.
if (n.right != null) {
return minValue (n.right);
}
// code for the second step in the above algorithm.
Node par = n.parent;
while (par != null && n == par.right) {
n = par;
par = par.parent;
}
return par;
}
/* Given a non-empty binary search
tree, return the minimum data
value found in that tree. Note that
the entire tree does not need
to be searched. */
Node minValue (Node node)
{
Node current_node = node;
/* loop down to find the leftmost leaf */
while (current_node.left != null) {
current_node = current_node.left;
}
return current_node;
}
// Driver program to test above functions
public static void main (String [] args)
{
BinaryTreeDemo tree = new BinaryTreeDemo();
Node root = null, temp = null, suc = null, min = null;
root = tree.insert (root, 19);
root = tree.insert (root, 7);
root = tree.insert (root, 21);
root = tree.insert (root, 3);
root = tree.insert (root, 11);
root = tree.insert (root, 9);
root = tree.insert (root, 13);
temp = root.left.right.left;
suc = tree.inOrderSuccessor (root, temp);
if (suc != null) {
System.out.println(
"The Inorder successor of "
+ temp.data + "node is " + suc.data);
}
else {
System.out.println(
"Inorder successor for that node does not exist!!");
}
} // main
} // BinaryTreeDemo.
OUTPUT:
The Inorder successor of 9 is 11.
Let’s look into all the complexities that the above program holds.
Time Complexity of the Inorder successor program is O(h), where h is the height of the binary search tree.
Space Complexity of the Inorder successor program is O(1). As this does not require any data structure while implementing the logic.
So, in this way we can find the Inorder successor using the parent pointer.
Method 2 – Searching from the root node.
In this method the main strategy we play is searching from the root node. So, there is no need of a parent pointer. This algorithm is also divided into two stages. This division is done on the basis of the right sub tree of the given node. One stage has the input node empty and the other stage having the input node filled.
In this algorithm the root node and the node for which the Inorder successor is needed is given as the input. The Inorder successor for that particular provided node is produced as the output.
The algorithm works on the following principles.
At first, we need to check weather the right sub tree of that node is NULL or not.
- If it is not NULL, then the Inorder successor of that node lies in the right sub tree. It is the node in the right sub tree having the minimum key value.
- If the right sub tree of the node is NULL, we should use the searching technique starting from the root node. Check if the node data is greater than the root data. If yes, travel down the right sub tree. If not travel down the left sub tree.
This is the working mechanism of the above algorithm.
Let’s look the implementation of the above algorithm in java programming language.
// Java program for above approach
class BinaryTreeDemo
{
/* A binary tree has three parts. The data part, a pointer to the left child of the node and a pointer to the right child of the node.
*/
static class node
{
int data;
node left;
node right;
node parent;
};
static node InOrderSuccessor (node root, node N)
{
// First step for the above algorithm
if (N.right != null)
return minValue(N.right);
node suc = null;
// Start searching from the root node for the Inorder successor down the tree.
while (root != null)
{
if (N.data < root.data)
{
suc = root;
root = root.left;
}
else if (N.data > root.data)
root = root.right;
else
break;
}
return suc;
}
/*
A non-empty binary tree is given which returns the minimum data value from that binary tree. A point to be noted is that, it is not necessary for searching the whole tree.
*/
static node minValue (node node)
{
node current_node = node;
/*
To find the left most leaf, we should apply loop for the nodes in the binary tree.
*/
while (current_node.left != null)
{
Current_node = current_node.left;
}
return current_node;
}
/*
This function helps in allocating the data value, null left pointer and null right pointer to the new node.
*/
static node newNode (int data)
{
node new_node = new node ();
new_node.data = data;
new_node.left = null;
new_node.right = null;
new_node.parent = null;
return (new_node);
}
/*
A binary search tree is given along with a number to insert a new node at a correct place using the number. After inserting this function returns a new root pointer which is used further in the program.
*/
static node insert (node node, int data)
{
/* 1. Check if the binary tree is empty. If yes, then return a new
Binary tree with a single node.
*/
if (node == null)
return (newNode(data));
else
{
node temp;
/* 2. If the tree is not empty, recur down the tree. */
if (data <= node.data)
{
temp = insert(node.left, data);
node.left = temp;
temp.parent = node;
}
else
{
temp = insert(node.right, data);
node.right = temp;
temp.parent = node;
}
/* return the (unchanged) node pointer */
return node;
}
}
/*
Driver code to test the above functions/ Methods
*/
public static void main (String [] args)
{
node root = null, temp, suc , min;
// creating the binary tree.
root = insert (root, 19);
root = insert (root, 7);
root = insert (root, 21);
root = insert (root, 3);
root = insert (root, 10);
root = insert (root, 9);
root = insert (root, 13);
temp = root.left.right.left;
// Function Call for the Inorder successor method.
suc = InOrderSuccessor(root, temp);
if (suc != null)
System.out.printf( "\n Inorder Successor of %d is %d ",
temp.data, suc.data);
else
System.out.printf("\n Inorder Successor doesn't exit");
}
}
OUTPUT:
The Inorder successor of 9 is 11.
Let’s look into all the complexities that the above program holds.
Time Complexity of the Inorder successor program is O(h), where h is the height of the binary search tree.
Space Complexity of the Inorder successor program is O(1). As this does not require any data structure while implementing the logic.
Method 3 – Inorder Traversal
Using the Inorder traversal also we can fin out the Inorder successor of a particular node. In the Inorder traversal, the first node greater than the value of current node is the Inorder traversal of the current node.
In this algorithm the root node and the node for which the Inorder successor is needed is given as the input. The Inorder successor for that particular provided node is produced as the output.
Let’s look the implementation of Inorder traversal using a java program.
// Java Program for the Inorder traversal of a Binary Search Tree
import java.util.*;
class InorderTraversalDemo {
/*
A binary search tree node has data, a left child pointer and a right child pointer.
*/
static class node {
int data;
node left;
node right;
node parent;
};
static void InOrderTraversal(node root) {
if (root == null) {
return;
}
InOrderTraversal(root.left);
System.out.print(root.data);
InOrderTraversal(root.right);
}
static void InOrderTraversal(node root, node n, node suc) {
if (root == null) {
return;
}
InOrderTraversal(root.left, n, suc);
if (root.data > n.data && suc.left == null) {
suc.left = root;
return;
}
InOrderTraversal(root.right, n, succ);
}
static node InOrderSuccessor(node root, node n) {
node suc = newNode(0);
InOrderTraversal(root, n, suc);
return suc.left;
}
/*
This function helps in allocating a new node with the given data and null left and right pointers.
*/
static node newNode(int data) {
node node = new node ();
node.data = data;
node.left = null;
node.right = null;
node.parent = null;
return (node);
}
/*
A binary search tree is given along with a number to insert a new node at a correct place using the number. After inserting this function returns a new root pointer which is used further in the program.
*/
static node insert (node node, int data) {
/*
1. check weather the tree is empty or not. If yes, then return the tree having the new node.
*/
if (node == null)
return (newNode (data));
else {
node temp;
/*
2. If the root node is not empty, recur down the tree
*/
if (data <= node.data) {
temp = insert (node.left, data);
node.left = temp;
temp.parent = node;
} else {
temp = insert (node.right, data);
node.right = temp;
temp.parent = node;
}
/*
A node pointer which is not changed should be returned.
*/
return node;
}
}
// Driver code for the above approach for the binary search tree.
public static void main (String [] args) {
node root = null, temp, suc, min;
// Creating the binary search tree by inserting these nodes.
root = insert (root, 20);
root = insert (root, 8);
root = insert (root, 22);
root = insert (root, 4);
root = insert (root, 12);
root = insert (root, 10);
root = insert (root, 14);
temp = root.left.right.left;
// Function Call to get the Inorder successor of temp.
suc = InOrderSuccessor(root, temp);
if (suc != null)
System.out.print("\n Inorder Successor of " + temp.data + " is " + suc.data);
else
System.out.print("\n Inorder Successor doesn't exist");
}
}OUTPUT:
The Inorder successor of 9 is 11.
Let’s look into all the complexities that the above program holds.
Time Complexity of the Inorder successor program is O(h), where h is the height of the binary search tree.
Space Complexity of the Inorder successor program is O(1). As it does not require any data structure while implementing the logic.
These are some of the methods to find the Inorder successor of a particular node.