Binary Search Trees: Find the Inorder predecessor and successor for a given key in BST

You are given BST root and a key, find the inorder predecessor and successor for that key.

If the key is not found, then you need to return the 2 values in which the key lies.

If the root is NULL then return.

If the key is found then if the left subtree is not NULL, then the predecessor will be the right most child of the left subtree or the left child itself.

If the key is found then if the right subtree is not NULL, then the successor will be the left most child of the right subtree or the right child itself.

If the key is smaller then root node, then,

set the successor as root search recursively into left subtree.

  else

set the predecessor as root search recursively into right subtree.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct Node
{
    int data;
    struct Node *left, *right;
};
 

void get_pre_succ(Node* root, Node*& pre, Node*& suc, int key)
{
    if (root == NULL)  return ;
 
    if (root->data == key)
    {
        if (root->left != NULL)
        {
            Node* tmp = root->left;
            while (tmp->right)
                tmp = tmp->right;
            pre = tmp ;
        }
 
        if (root->right != NULL)
        {
            Node* tmp = root->right ;
            while (tmp->left)
                tmp = tmp->left ;
            suc = tmp ;
        }
        return ;
    }
 
    if (root->data > key)
    {
        suc = root ;
        get_pre_succ(root->left, pre, suc, key) ;
    }
    else
    {
        pre = root ;
        get_pre_succ(root->right, pre, suc, key) ;
    }
}
 
Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* insert_into_bst(Node* node, int key)
{
    if (node == NULL) return get_new_node(key);
    if (key < node->data)
        node->left  = insert_into_bst(node->left, key);
    else
        node->right = insert_into_bst(node->right, key);
    return node;
}
 
int main()
{
    int key = 6; 
 
   /* 
              5
           /     \
          3       7
         /  \    /  \
         2   4   6   8  */
    Node *root = NULL;
    root = insert_into_bst(root, 5);
    insert_into_bst(root, 3);
    insert_into_bst(root, 2);
    insert_into_bst(root, 4);
    insert_into_bst(root, 7);
    insert_into_bst(root, 6);
    insert_into_bst(root, 8);
 
 
    Node *pre = NULL, *suc = NULL;
 
    get_pre_succ(root, pre, suc, key);
    if (pre != NULL)
      cout << "Predecessor is " << pre->data << endl;
    else
      cout << "No Predecessor";
 
    if (suc != NULL)
      cout << "Successor is " << suc->data;
    else
      cout << "No Successor";
    return 0;
}

Output:

Predecessor is 5
Successor is 7