Inorder Successor in a binary search tree.cpp

// https://www.youtube.com/watch?v=5cPbNCrdotA
// we are trying to find next higher value
struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
}
// function to find In order successor in a BST

// find left minimum
struct Node * Find(struct *Node root, int data)
{
    if (root == NULL)
    {
        return NULL;
    }
    while (root->left != NULL)
    {
        root = root->left;
    }
    return root;
}

struct Node * GetSuccessor(struct Node *root, int data)
{
    struct Node *current = Find(root, data);
    if (current == NULL)
    {
        return NULL;
    }
    // Case 1: node has right subtree
    // go to left most minimum item
    if (current->right != NULL)
    {
        struct Node *temp = current->right;
        while (temp->left != NULL)
        {
            temp = temp->left;
        }
        return temp;
    }
    else
    {
        // Case 2: no right sub tree
        // start from root and find first ancestor
        struct Node *successor = NULL;
        struct Node *ancestor = root;
        while (ancestor != current)
        {
            if (current->data < ancestor->data)
            {
                // so far this is the deepest node for
                // which current node is in left
                successor = ancestor;
                ancestor = ancestor->left;
            }
            else
            {
                ancestor = ancestor->right;
            }
        }
        return successor;
    }
}