-
-
Save mycodeschool/6515e1ec66482faf9d79 to your computer and use it in GitHub Desktop.
/* 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"; | |
} |
Yaa ur are right Anu it should be int
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!
Line 54 should be like this : cout<<root->data<<" "; //Print data
Because we are in c++ right now :D
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!
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
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
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;
}
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;
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,
AnuNo, 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).
Is find function necessary?
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
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
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
Line 54 should be like this :
cout<<root->data<<" "; //Print data
Because we are in c++ right now :D
Hey Resul,
C++ supports backward compatibility from C, making it easier to use either of the syntaxes " cout<< " or printf(" %d ", root-> data ) .
Though, I agree each of these "print function to console" has different uses and applications.
Check this out for a better idea :
https://stackoverflow.com/questions/2872543/printf-vs-cout-in-c
Cheers.
` /* C++ program to find Inorder successor in a BST */
#include
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 maximum value in a BST
struct Node* FindMax(struct Node* root) {
if(root == NULL) return NULL;
while(root->right != NULL)
root = root->right;
return root;
}
//Function to find Inorder Predecessor in a BST
struct Node* Getpredecessor (struct Node* root,int data) {
// Search the Node - O(h)
struct Node* current = Find(root,data);
if(current == NULL) return NULL;
if(current->left != NULL) { //Case 1: Node has left subtree
return FindMax(current->left); // O(h)
}
else { //Case 2: No left subtree - O(h)
struct Node* predecessor = NULL;
struct Node* ancestor = root;
while(ancestor != current) {
if(current->data > ancestor->data) {
if(ancestor->data < current->data)
predecessor = ancestor; // so far this is the deepest node for which current node is in right
ancestor = ancestor->right;
}
else
ancestor = ancestor->left;
}
return predecessor ;
}
}
//Function to visit nodes in Inorder
void Inorder(Node *root) {
if(root == NULL) return;
Inorder(root->left); //Visit right subtree
printf("%d ",root->data); //Print data
Inorder(root->right); // Visit right subtree
}
//Function to visit nodes in Postorder
void Postorder(Node *root) {
if(root == NULL) return;
Postorder(root->right); //Visit right subtree
printf("%d ",root->data); //Print data
Postorder(root->left); // 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<<"Postorder Traversal: ";
Postorder(root);
cout<<"\n";
// Find Inorder successor of some node.
struct Node* predecessor = Getpredecessor(root,8);
if(predecessor == NULL) cout<<"No predecessor Found\n";
else
cout<<"Predecessor is "<<predecessor->data<<"\n";
}
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->data==data){
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);
}
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