Where to Find the Inorder Successor?
To find the inorder successor of a node in a binary search tree (BST), you can start at the root and traverse the tree down to the node whose successor you want to find. Once you have found the node, there are two cases to consider: if the node has a right subtree, the successor will be the leftmost node in that subtree. Otherwise, you need to go up the tree to the first ancestor node whose left child is also an ancestor of the original node. The successor will be the value of that ancestor node.
Method 1: Uses Parent Pointer
The parent pointer is used to find the inorder successor of a node in a binary search tree (BST) uses a parent pointer. This method requires that each node in the BST stores a pointer to its parent node, allowing us to traverse up the tree to find the successor node.
Implementation in C++
The implementation of this method in c++ is given below.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node* parent;
};
Node* inorderSuccessor(Node* node) {
if (node == NULL) return NULL;
if (node->right != NULL) {
node = node->right;
while (node->left != NULL)
node = node->left;
return node;
}
while (node->parent != NULL && node == node->parent->right)
node = node->parent;
return node->parent;
}
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return node;
}
int main() {
Node* root = newNode(10);
root->left = newNode(5);
root->right = newNode(15);
root->left->parent = root;
root->right->parent = root;
root->left->left = newNode(3);
root->left->right = newNode(8);
root->left->left->parent = root->left;
root->left->right->parent = root->left;
Node* successor = inorderSuccessor(root->left->right);
if (successor != NULL)
cout << "The inorder successor of " << root->left->right->data << " is " << successor->data << endl;
else
cout << "The inorder successor of " << root->left->right->data << " is NULL" << endl;
return 0;
}
Output
The inorder successor of 8 is 10
Method 2: Search from root
This method is used to find the inorder successor of a node in a binary search tree (BST) and involves traversing the tree from the root to the given node while maintaining a variable to keep track of the last node that was greater than the given node.
Implementation in C++
The implementation of this method in c++ is given below.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* inorderSuccessor(Node* root, Node* node) {
if (node == NULL) return NULL;
if (node->right != NULL) {
node = node->right;
while (node->left != NULL)
node = node->left;
return node;
}
Node* succ = NULL;
while (root != NULL) {
if (node->data < root->data) {
succ = root;
root = root->left;
}
else if (node->data > root->data)
root = root->right;
else
break;
}
return succ;
}
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
Node* root = newNode(10);
root->left = newNode(5);
root->right = newNode(15);
root->left->left = newNode(3);
root->left->right = newNode(8);
Node* successor = inorderSuccessor(root, root->left->right);
if (successor != NULL)
cout << "The inorder successor of " << root->left->right->data << " is " << successor->data << endl;
else
cout << "The inorder successor of " << root->left->right->data << " is NULL" << endl;
return 0;
}
Output
The inorder successor of 8 is 10
Method 3: Inorder traversal
This method is used to find the inorder successor of a node in a binary search tree (BST) and involves performing an inorder traversal of the tree and maintaining a variable to keep track of the last node visited. When we visit the given node during the traversal, the next node we visit will be its inorder successor.
Implementation in C++
The implementation of this method in c++ is given below.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
void inorder(Node* root, Node* &prev, Node* &succ, int key) {
if (root == NULL) return;
inorder(root->left, prev, succ, key);
if (prev != NULL && prev->data == key)
succ = root;
prev = root;
inorder(root->right, prev, succ, key);
}
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
Node* root = newNode(10);
root->left = newNode(5);
root->right = newNode(15);
root->left->left = newNode(3);
root->left->right = newNode(8);
Node* prev = NULL, *succ = NULL;
inorder(root, prev, succ, 8);
if (succ != NULL)
cout << "The inorder successor of 8 is " << succ->data << endl;
else
cout << "The inorder successor of 8 is NULL" << endl;
return 0;
}
Output
The inorder successor of 8 is 10
Method 4: Inorder traversal iterative
This method is used to find the inorder successor of a node in a binary search tree (BST) and involves performing an iterative inorder traversal of the tree using a stack and maintaining a boolean variable to keep track of whether we have found the given node yet. When we pop the given node off the stack during the traversal, the next node we pop off the stack will be its inorder successor.
Implementation in C++
The implementation of this method in c++ is given below.
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* inorderSuccessor(Node* root, Node* node) {
stack<Node*> s;
Node* curr = root;
bool found = false;
while (!s.empty() || curr != NULL) {
while (curr != NULL) {
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
if (found)
return curr;
if (curr == node)
found = true;
curr = curr->right;
}
return NULL;
}
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
Node* root = newNode(10);
root->left = newNode(5);
root->right = newNode(15);
root->left->left = newNode(3);
root->left->right = newNode(8);
Node* succ = inorderSuccessor(root, root->left->right);
if (succ != NULL)
cout << "The inorder successor of " << root->left->right->data << " is " << succ->data << endl;
else
cout << "The inorder successor of " << root->left->right->data << " is NULL" << endl;
return 0;
}
Output
The inorder successor of 8 is 10
Frequently Asked Questions
What is an in-order Successor in a binary search tree?
The Inorder Successor of a given key in the Binary Search Tree is the node that appears just after the provided key node in the inorder traversal of the BST.
What are the time and space complexities of finding an in-order Successor in a binary search tree?
Time Complexity: O(n), where ‘n’ is the number of nodes in BST.
Space complexity: O(1), or we can say that it has a constant space complexity.
How do you find the inorder successor of a node in BST?
To find the inorder successor of a node in a Binary Search Tree (BST), we first determine if the node has the right child. If it does, the inorder successor is the leftmost node in the right subtree. If it doesn't, we traverse up the tree until we find a node whose left child is an ancestor of the original node. This node is the inorder successor.
What is predecessor and successor in BST?
In a Binary Search Tree (BST), the predecessor of a node is the largest node that is smaller than the given node. The successor of a node is the smallest node that is larger than the given node. These nodes can be used to perform various operations such as deleting a node or finding the minimum or maximum value in the tree.
Conclusion
In this blog, we discussed how to find the the Inorder Successor of a given key in a Binary Search Tree with different approaches and code.
Recommended Reading:
Recommended problems -
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
305+ registered