DSA interview question

Inorder Predecessor and Successor in a BST

Medium · Algorithms · Topics: bst

The problem

A scheduling system keeps booked time slots in a BST. For any requested time (booked or not), the UI shows the previous booked slot (the largest key strictly less than it: the inorder predecessor) and the next booked slot (the smallest key strictly greater: the inorder successor). As with floor and ceil, both candidates lie on the search path. While walking down, a node smaller than the key is the best predecessor so far and the search goes right; a node larger is the best successor so far and the search goes left. On an exact match, go both ways, since the answers are then the extremes of its two subtrees.

Example: BST [50, 30, 70, 20, 40, 60, 80], key 65 → predecessor 60, successor 70.

Function signature

pair<int, int> predSucc(TreeNode* root, int key);  // {predecessor, successor}; -1 if missing

Test cases

Input `(tree, key)`	Output	Explanation
`([50,30,70,20,40,60,80], 65)`	`pre 60 suc 70`	65 isn't in the tree
`([50,30,70,20,40,60,80], 50)`	`pre 40 suc 60`	Strictly less and strictly greater
`([50,30,70,20,40,60,80], 20)`	`pre -1 suc 30`	No smaller key
`([50,30,70,20,40,60,80], 80)`	`pre 70 suc -1`	No larger key
`([50,30,70,20,40,60,80], 45)`	`pre 40 suc 50`

(Confirm: predecessor and successor are strict; keys are distinct and positive, so −1 means none.)

How interviewers phrase it

"Find the inorder predecessor and successor of a given key in a BST; the key may not be present" (GeeksforGeeks "Predecessor and Successor").

Clarifying questions to ask

Strict (< and >) or inclusive? (Strict.)
Can the key be absent from the tree? (Yes.)
What should be returned when there's no predecessor or successor? (−1 or null.)

Follow-ups to expect

"Why can both be found in one walk?"
"What happens when the key is found?"
"Given a node pointer (LeetCode 285), how do you find the successor?"
"With parent pointers?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview