Skip to content

Instantly share code, notes, and snippets.

Last active October 29, 2023 09:20
Show Gist options
  • Save mycodeschool/6515e1ec66482faf9d79 to your computer and use it in GitHub Desktop.
Save mycodeschool/6515e1ec66482faf9d79 to your computer and use it in GitHub Desktop.
C++ program to find Inorder successor in a BST
/* C++ program to find Inorder successor in a BST */
using namespace std;
struct Node {
int data;
struct Node *left;
struct Node *right;
//Function to find some data in the tree
Node* Find(Node*root, int data) {
if(root == NULL) return NULL;
else if(root->data == data) return root;
else if(root->data < data) return Find(root->right,data);
else return Find(root->left,data);
//Function to find Node with minimum value in a BST
struct Node* FindMin(struct Node* root) {
if(root == NULL) return NULL;
while(root->left != NULL)
root = root->left;
return root;
//Function to find Inorder Successor in a BST
struct Node* Getsuccessor(struct Node* root,int data) {
// Search the Node - O(h)
struct Node* current = Find(root,data);
if(current == NULL) return NULL;
if(current->right != NULL) { //Case 1: Node has right subtree
return FindMin(current->right); // O(h)
else { //Case 2: No right subtree - O(h)
struct Node* successor = NULL;
struct Node* ancestor = root;
while(ancestor != current) {
if(current->data < ancestor->data) {
successor = ancestor; // so far this is the deepest node for which current node is in left
ancestor = ancestor->left;
ancestor = ancestor->right;
return successor;
//Function to visit nodes in Inorder
void Inorder(Node *root) {
if(root == NULL) return;
Inorder(root->left); //Visit left subtree
printf("%d ",root->data); //Print data
Inorder(root->right); // Visit right subtree
// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
if(root == NULL) {
root = new Node();
root->data = data;
root->left = root->right = NULL;
else if(data <= root->data)
root->left = Insert(root->left,data);
root->right = Insert(root->right,data);
return root;
int main() {
/*Code To Test the logic
Creating an example tree
/ \
3 10
/ \ \
1 4 11
Node* root = NULL;
root = Insert(root,5); root = Insert(root,10);
root = Insert(root,3); root = Insert(root,4);
root = Insert(root,1); root = Insert(root,11);
//Print Nodes in Inorder
cout<<"Inorder Traversal: ";
// Find Inorder successor of some node.
struct Node* successor = Getsuccessor(root,1);
if(successor == NULL) cout<<"No successor Found\n";
cout<<"Successor is "<<successor->data<<"\n";
Copy link

asesami commented Dec 4, 2021

i dont know if its good practice, but it a different faster implementation in trade off for higher memory requierements

Node* successor(Node * root, int data, Node * ancestor=NULL){
	//if found, return either right sub or ancestor
		if(root->right!=NULL)return root->right;
		else return ancestor;
	// search for Node, if call for left sub, give self as arg
	if (data<root->data)return successor(root->left, data, root);
	else return successor(root->right, data, ancestor);

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment