Quick actions

cmd+k|ctrl+k

Navigation

Languages

Find Inorder successor in a BST

Snippet info

Language

Cpp

Visibility

public

Author

varun.muriyanat

Created

2025-05-12T22:44:24.660715Z

Updated

2025-05-12T23:04:39.576357Z

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