Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
C++ program to find Inorder successor in a BST
/* C++ program to find Inorder successor in a BST */
#include<iostream>
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;
}
else
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);
else
root->right = Insert(root->right,data);
return root;
}
int main() {
/*Code To Test the logic
Creating an example tree
5
/ \
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: ";
Inorder(root);
cout<<"\n";
// Find Inorder successor of some node.
struct Node* successor = Getsuccessor(root,1);
if(successor == NULL) cout<<"No successor Found\n";
else
cout<<"Successor is "<<successor->data<<"\n";
}
@anumercian

This comment has been minimized.

Copy link

@anumercian anumercian commented May 26, 2015

Dear Code School;

Shouldn't the data-type for "data" in Line 59, be int? Cause the struct has "data" as int.

https://gist.github.com/mycodeschool/6515e1ec66482faf9d79#file-bst_inordersuccessor_cpp-cpp-L59

Thanks,
Anu

@sandeepvarma123

This comment has been minimized.

Copy link

@sandeepvarma123 sandeepvarma123 commented Jun 13, 2016

Yaa ur are right Anu it should be int

@RainMaker97

This comment has been minimized.

Copy link

@RainMaker97 RainMaker97 commented Jul 24, 2016

Hey!
Can you tell me why we didn't just use a FindMax() function for the left subtree like we used the FindMin() function for the right?
Is it because of the time complexity? But then wouldn't it take as much time as the FindMax() function?
This is really bugging me, any clarity would help!

@MuhammedResulBilkil

This comment has been minimized.

Copy link

@MuhammedResulBilkil MuhammedResulBilkil commented Jan 7, 2017

Line 54 should be like this : cout<<root->data<<" "; //Print data
Because we are in c++ right now :D

@rishijd

This comment has been minimized.

Copy link

@rishijd rishijd commented Apr 16, 2018

Python version: https://github.com/rishijd/python-learning/blob/master/data-structures/trees-inorder-successor.py

Even though this was created in 2014, it is so useful today. Thank you!

@jigar288

This comment has been minimized.

Copy link

@jigar288 jigar288 commented Aug 23, 2018

shouldn't line 14 be with this greater than "else if(root->data > data) return Find(root->right,data);" instead of less than "else if(root->data < data) return Find(root->right,data);" because if a node is greater than you search right node left

@adarsh115

This comment has been minimized.

Copy link

@adarsh115 adarsh115 commented Nov 18, 2018

Dear Code School;

Shouldn't the data-type for "data" in Line 59, be int? Cause the struct has "data" as int.

https://gist.github.com/mycodeschool/6515e1ec66482faf9d79#file-bst_inordersuccessor_cpp-cpp-L59

Thanks,
Anu

he may have written it bymistake

@vinaychatra

This comment has been minimized.

Copy link

@vinaychatra vinaychatra commented Feb 11, 2019

A more simpler program in java which takes care of both the cases

public TreeNode getSuccessor(TreeNode a, int b) {
       TreeNode res=null;
       TreeNode cur=a;
       while(cur!=null){
           if(cur.val>b){
               res=cur;
               cur=cur.left;
            }else{
               cur=cur.right;
           }
       }
       return res;
   }
@AdarshPawar29

This comment has been minimized.

Copy link

@AdarshPawar29 AdarshPawar29 commented Mar 25, 2019

Dear Code School;

Shouldn't the data-type for "data" in Line 59, be int? Cause the struct has "data" as int.

https://gist.github.com/mycodeschool/6515e1ec66482faf9d79#file-bst_inordersuccessor_cpp-cpp-L59

Thanks,
Anu

No, It's right. It would be int when that function returns return root->data;

@IMSUMEET

This comment has been minimized.

Copy link

@IMSUMEET IMSUMEET commented Aug 14, 2020

Dear Code School;
Shouldn't the data-type for "data" in Line 59, be int? Cause the struct has "data" as int.
https://gist.github.com/mycodeschool/6515e1ec66482faf9d79#file-bst_inordersuccessor_cpp-cpp-L59
Thanks,
Anu

No, It's right. It would be int when that function returns return root->data;

No Adarsh , Anu is not asking about the return type but the data type! And it is supposed to be int since integer(int) is passed to the insert function, not a character(char).

@JESSE-max1

This comment has been minimized.

Copy link

@JESSE-max1 JESSE-max1 commented Aug 16, 2020

Is find function necessary?

@abhnvjn

This comment has been minimized.

Copy link

@abhnvjn abhnvjn commented Oct 6, 2020

We also need to write some condition to handle the maximium element in the BST, in this case 11, if we try to find inorder successor of 11, this gives 5 as the answer. So adding 1 more if condition to the Getsuccessor() will work fine.
if(data == maxelementintree) return NULL

@ajkrsna45

This comment has been minimized.

Copy link

@ajkrsna45 ajkrsna45 commented Nov 26, 2020

Line 54 should be like this : cout<<root->data<<" "; //Print data
Because we are in c++ right now :D

Yes it should be in C++ print form

@iachieve

This comment has been minimized.

Copy link

@iachieve iachieve commented Dec 23, 2020

A more simpler program in java which takes care of both the cases

public TreeNode getSuccessor(TreeNode a, int b) {
       TreeNode res=null;
       TreeNode cur=a;
       while(cur!=null){
           if(cur.val>b){
               res=cur;
               cur=cur.left;
            }else{
               cur=cur.right;
           }
       }
       return res;
   }

awesome

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