Problem:
There is BST given with root node with key part as an integer only. You need to find the in-order successor and predecessor of a given key. If either predecessor or successor is not found, then set it to NULL.

Input:
The root of BST is given with nodes pre, suc and int key which successor and predecessor need to be found.

Output:
Find the predecessor and successor of the key in BST and sets pre and suc as predecessor and successor, respectively Otherwise, set to NULL.

Note: You don't need to print anything. You only need to set p.pre to the predecessor and s.succ to the successor. p and s have been passed in the function parameter.

Constraints:
1<=T<=100
1<=n<=100
1<=data of node<=100
1<=key<=100

Example:
Input:
root = [6,2,8,0,4,7,9,null,null,3,5], pre=NULL, suc=NULL, key=8

Output:
pre=7, suc=9

Code:

/* BST Node
struct Node
{
	int key;
	struct Node *left, *right;
};
*/

// This function finds predecessor and successor of key in BST.
// It sets pre and suc as predecessor and successor respectively

Node* successor(Node* root, Node*& suc, int key)
{
    while(root)
    {
        if(root->key <= key)
            root=root->right;
        else
        {
            suc=root;
            root=root->left;
        }
    }
    return suc;
}

Node* predecessor(Node* root, Node*& pre, int key)
{
    while(root)
    {
        if(root->key >= key)
            root=root->left;
        else
        {
            pre=root;
            root=root->right;
        }
    }
    return pre;
}
void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)
{
    successor(root, suc, key);
    predecessor(root, pre, key);

}

Reference: GFG