'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before', 'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before',
Update appNew update is available. Click here to update.
Topics

Predecessor and Successor In BST

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
21 upvotes
Asked in companies
OlaDirectiGoldman Sachs

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