Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Predecessor and Successor In BST

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
23 upvotes
Asked in companies
GoogleGoldman SachsDirecti

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:

alttext

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
Full screen
Console