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

Public snippets