Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is an inorder successor of a BST?
3.
Where to Find the Inorder Successor?
4.
Method 1: Uses Parent Pointer
4.1.
Implementation in C++
5.
Method 2: Search from root
5.1.
Implementation in C++
6.
Method 3: Inorder traversal
6.1.
Implementation in C++
7.
Method 4: Inorder traversal iterative
7.1.
Implementation in C++
8.
Frequently Asked Questions
8.1.
What is an in-order Successor in a binary search tree?
8.2.
What are the time and space complexities of finding an in-order Successor in a binary search tree?
8.3.
How do you find the inorder successor of a node in BST?
8.4.
What is predecessor and successor in BST?
9.
Conclusion
Last Updated: Jun 10, 2024
Medium

# Inorder Successor in BST (Binary Search Tree)

## Introduction

Before diving into our topic, “In order Successor of a given key In Binary Search Tree.” Let’s first understand basic terms related to our topic.

Also see, Data Structures

## What is an inorder successor of a BST?

Inorder traversal is a method used to visit every node in a binary tree, where the left subtree is visited first, then the current node, and finally the right subtree. This algorithm is used to traverse binary search trees, and it allows the nodes to be visited in a specific order, useful for various applications.

It is one of the ways to traverse the given binary tree such that the elements are ordered in such a way that the left node comes before the root node, and the right node comes after the root node.

LEFT -> ROOT -> RIGHT

We can remember this by the keyword ‘IN’, meaning that the root node should come in between the left and right nodes.

Similarly, in pre-order and post-order, the root node should come ‘PRE’ (before left node) and POST’ (after right node), respectively.

OKAY, now that the inorder traversal is clear, let’s see the main properties of Binary Search Trees.

A Binary Search Tree is a Binary Tree (obviously), so in BSTs, each node can have at most two children. But BSTs also have one interesting property: each node in a BST is greater than the maximum node in its left subtree and lesser than the minimum node in its right subtree.

Let’s see an example:

If we observe the given Binary Tree, we can tell that it is a Binary Search Tree because the value of each node is greater than the maximum valued node in its left subtree and is lesser than the minimum valued node in its right subtree.

For instance, take node 50, the maximum valued node in its left subtree is 45, and the minimum valued node in its right subtree is 55.

If we print the Inorder Traversal for this BST, we’ll get:

10 35 40 45 50 55 70 100 150

See, the elements are in ascending order. That brings us to another interesting fact related to BSTs: the inorder traversal of a BST gives us elements in ascending order sorted manner.

NOW, coming on to the main topic of this blog, “Inorder Successor of a given key In 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.

From our above example, we can say that the Inorder Successor of, let’s say, 35 is 40 because, in the inorder traversal of BST, it is coming just after 35. For 50, it will be 55, and so on.

Kudos! Now you have understood all the essential things needed, and the only thing left is to write code to find the in-order successor of a given key In the Binary Search Tree.

Recommended: Try The Problem yourself before moving on to the solution.

## 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.

Live masterclass