Problem Statement

There is BST given with root node with key part as integer only. You need to find the inorder successor and predecessor of a given key. In case, if the either of predecessor or successor is not found print -1.

**Input:**The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains n denoting the number of edges of the BST. The next line contains the edges of the BST. The last line contains the key.

**Output:**Print the predecessor followed by successor for the given key. If the predecessor or successor is not found print -1.

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

Example:

Input:

2

6

50 30 L 30 20 L 30 40 R 50 70 R 70 60 L 70 80 R65650 30 L 30 20 L 30 40 R 50 70 R 70 60 L 70 80 R100

Output:

60 70

80 -1

Problem Link

Predecessor and Successor | Practice | GeeksforGeeks

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 *p,*s;
int f1,f2;
void rinorder(Node* root,int key)
{
    if(!root)
    return;
    
    rinorder(root->right,key);
    
    if(root->key<key&&f1)
    {
        p = root;
        f1 = 0;// so that p does not gets updated more than once
        return;
    }
    
    rinorder(root->left,key);
    
}

void inorder(Node* root,int key)
{
    if(!root)
    return;
    
    inorder(root->left,key);
    
    if(root->key>key&&f2)
    {
        s = root;
        f2 = 0;// so that s does not gets updated more than once
        return;
    }
    
    inorder(root->right,key);
    
}

void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)
{

    if(!root)
    return;
    
    p = s = NULL;
    f1 = f2 = 1;
    rinorder(root,key);
    pre = p;
    inorder(root,key);
    suc = s; 
}

Time Complexity: O(n)