Introduction
Binary trees are the specialized version of generic trees where every node can have only two children viz. the left child and the right child of a binary tree. In the following article, we are going to discuss some approaches for obtaining the inorder successor of a node in a binary tree.
Inorder traversal of the tree dictates that the nodes be processed in the left, root and the right manner, i.e., the leftmost child is printed first, then the root node, and finally the right child of the root node. Now since you have a basic understanding of the term inorder, let’s move on to the question. We are asked to print the inorder successor of a node in a binary tree.
The in-order successor of a node implies that we have to return the node which will come next in the inorder traversal of a binary tree. Let us see an example:
The inorder traversal for the above binary tree is: 4 2 5 1 6 3 7
In the above example, the inorder successor of 4 is 2. Similarly, the inorder successor of 5 is 1. Now it is natural to wonder what if the inorder successor of the last node is asked? What then? Well, it's pretty simple since there is no inorder successor for the last node (here 7) we simply consider NULL as their inorder successor. Therefore the inorder successor of 7 here is NULL.
Now that the term inorder successor of a binary tree is clear, let's move on towards an algorithm that will help us find the inorder successor of a given node in a binary tree.
Before moving forward to the solution it is recommended to try the problem by yourself first. Inorder Successor Problem
Approach 1
While discussing this approach, you have to keep this one thing in mind, i.e., Inorder traversal of a binary tree follows the order: Left child of node----> node -----> Right child of the node. Let us discuss the cases we need to consider while finding the inorder successor of a given node.
Case 1. The right child of the given node exists
Suppose the right child of the given binary tree is not NULL, then, in this case, the inorder successor of the given node will be the leftmost child of the right subtree.
Case 2. The right child of the given node is NULL
Now let’s discuss the case where a right child of a given binary tree is NULL i.e the tree is not having any right subtree. Think about this! So in this case it will travel up to the binary tree to find the parent node and will check if the current node is the left child of that parent node. If yes then stop you have found your answer; otherwise, continue traversing up the binary tree.
Case 3. The given node is the rightmost node of the binary tree
Suppose we are asked to give the inorder successor of the node which is the rightmost node of the binary tree. In this case, the answer will be NULL as discussed in the example above for node 7.
Let us now implement the above-discussed approach to find the inorder successor of a given node in the binary tree.
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
//Binary Tree Node class
class Node {
public:
//data members
int data;
Node * left;
Node * right;
//constructor
Node(int data) {
this -> data = data;
this -> left = NULL;
this -> right = NULL;
}
};
// function for finding the leftmost node in a tree
Node * leftMost(Node * node) {
while (node != NULL && node -> left != NULL)
node = node -> left;
return node;
}
// function for finding the rightmost node in a tree
Node * rightMost(Node * node) {
while (node != NULL && node -> right != NULL)
node = node -> right;
return node;
}
// recursive function for finding the Inorder Successor
Node * temp = new Node(-1);
Node * findInorderRecursive(Node * root, Node * x) {
if (root == NULL)
return NULL;
if (root == x || (temp = findInorderRecursive(root -> left, x)) ||
(temp = findInorderRecursive(root -> right, x))) {
if (temp) {
if (root -> left == temp) {
cout << "Inorder Successor of " << x -> data;
cout << " is " << root -> data << "\n";
return NULL;
}
}
return root;
}
return NULL;
}
// Function for finding the inorder successor of given target node x
void getInorderSuccessor(Node * root, Node * x) {
// Case1: If right child of given node is not NULL
if (x -> right != NULL) {
//leftmost child of right subtree will be the ans
Node * inorderAns = leftMost(x -> right);
cout << "Inorder Successor of " << x -> data << " is ";
cout << inorderAns -> data << "\n";
}
// Case2: If right child of given node is NULL
if (x -> right == NULL) {
Node * ans = rightMost(root);
// Case3: If x is the last node in the right subtree
if (ans == x)
cout << "No inorder successor exist because it is the right most node.\n";
else
//traverse up the tree
findInorderRecursive(root, x);
}
}
// Driver program to test above functions
int main() {
//creating the binary tree
Node * root = new Node(1);
root -> left = new Node(2);
root -> right = new Node(3);
root -> left -> left = new Node(4);
root -> left -> right = new Node(5);
root -> right -> left = new Node(6);
root -> right -> right = new Node(7);
// Case 1: When the right child of the target node is not NULL.
getInorderSuccessor(root, root);
// Case 2: When the right child of the target node is NULL
getInorderSuccessor(root, root -> left -> left);
// Case 3: When the target node is the rightmost node of the binary tree
getInorderSuccessor(root, root -> right -> right);
return 0;
}
Output:
Inorder Successor of 1 is 6
Inorder Successor of 4 is 2
No inorder successor exists because it is the rightmost node.Complexity Analysis
Time Complexity: The time complexity of the above approach is O(N), where N is the number of nodes in the binary tree.
Space Complexity: The space complexity of the above approach is O(H), where H is the height of the binary tree. There can be a skewed tree where H will be equal to the number of nodes in the binary tree for the worst-case scenario. Hence in the worst-case space complexity will be O(N).
As is with most problems, there can be multiple possible solutions for this one as well. Let us discuss another approach:
Also check out - Inorder Predecessor
19+ registered 
