Instantly share code, notes, and snippets.

mycodeschool/BST_InorderSuccessor_CPP.cpp

Last active October 29, 2023 09:20
Show Gist options
• Save mycodeschool/6515e1ec66482faf9d79 to your computer and use it in GitHub Desktop.
C++ program to find Inorder successor in a BST
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* 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 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 "<data<<"\n"; }

kamalinio21 commented Sep 25, 2021

` /* 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";

}

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->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);
}

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