New update is available. Click here to update.
Topics

# Predecessor and Successor In BST

Moderate
0/80
Average time to solve is 25m
Contributed by

## Problem statement

Given a binary search tree of integers containing 'N' nodes. You have also been given an integer X.

Your task is to find the inorder successor and predecessor of the given X. Formally, print an array/list containing the inorder predecessor and successor in the same order.

For Example:
``````For the BST given below:
``````

``````The inorder predecessor of 6 is 4.
The inorder successor of 6 is 7.
The inorder predecessor of 10 is 8.
The inorder successor of 10 is 13.
``````

Note:

``````If there is no inorder predecessor or successor of 'X', then add -1 to the answer vector in its place.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 5
1 <= N <= 5000
0 <= DATA <= 10^9
0 <= X <= 10^9

Where 'DATA' is the value of any node in the BST.

Time Limit: 1sec
``````
Sample Input 1:
``````1
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
5
``````
Sample Output 1:
``````2 6
``````

#### Explanation of the Sample Input 1:

``````For the given ‘X’ = 5, according to the inorder view, 2 is the parent of the left subtree and 6 is the parent of the right subtree, hence 2 and 6 are inorder predecessors and successor respectively.
``````
Sample Input 2:
``````2
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
6
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
2
``````
Sample Output 2:
``````5 7
-1 5
``````
Console