Find Inorder successor in a BST
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
#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 the 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) {
struct Node* current = Find(root, data); //search the node O(h)
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 the left subtree
cout << root->data << ", "; // visit the node
Inorder(root->right); // Visit the 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() {
/*
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, 10);
if (successor == NULL) cout << "No successor found\n";
else cout << "Successor is " << successor->data << "\n";
return 0;
}
Cpp
INFO