Log inSign up
mediumGeeksforGeeksNot Started

Predecessor and Successor in BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a Binary Search Tree (BST) and a key, find the in-order predecessor and in-order successor of the given key in the BST.

- Predecessor: The node with the largest value strictly less than key. - Successor: The node with the smallest value strictly greater than key.

If either does not exist, leave its reference as null / nullptr. Notice that the key does not necessarily have to exist in the BST.

Constraints:

  • 1 <= Number of nodes <= 105
  • 1 <= Node.data <= 106
  • 1 <= key <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the dual relationship between inorder predecessor and successor.
  • Handle cases where key is present vs not present in the tree.
  • Implement the O(H) time and O(1) space iterative search.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find predecessor and successor in BST.
  • Closest smaller and larger elements.
  • Single pass BST boundary search.

Algorithmic Decision Tree:

  • If key < curr.data: suc = curr; curr = curr.left.
  • If key > curr.data: pre = curr; curr = curr.right.
  • If key == curr.data: check subtrees directly.

Connected Patterns:

Inorder Successor in BSTFloor in BSTCeil in BST

1. Full Inorder Array Scan

Intuition

Traverse the tree inorder and record values in an array. Iterate through the array to find the last value < key (predecessor) and the first value > key (successor). Takes O(N) time and O(N) space.

When to apply: Baseline comparison when space is unrestricted.

Algorithm

  1. Extract sorted array via inorder traversal, then find the largest element < key and smallest element > key.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct Node {
5 int data;
6 Node* left;
7 Node* right;
8 Node(int val) : data(val), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(Node* root, std::vector<Node*>& nodes) {
13 if (!root) return;
14 inorder(root->left, nodes);
15 nodes.push_back(root);
16 inorder(root->right, nodes);
17 }
18public:
19 void findPreSuc(Node* root, Node*& pre, Node*& suc, int key) {
20 pre = nullptr;
21 suc = nullptr;
22 std::vector<Node*> nodes;
23 inorder(root, nodes);
24
25 for (Node* node : nodes) {
26 if (node->data < key) pre = node;
27 if (node->data > key && !suc) suc = node;
28 }
29 }
30};
31
32int main() {
33 Node* root = new Node(50);
34 root->left = new Node(30);
35 root->right = new Node(70);
36 root->left->left = new Node(20);
37 root->left->right = new Node(40);
38 root->right->left = new Node(60);
39 root->right->right = new Node(80);
40
41 Solution sol;
42 Node *pre = nullptr, *suc = nullptr;
43 sol.findPreSuc(root, pre, suc, 65);
44 std::cout << "Pre: " << (pre ? pre->data : -1) << ", Suc: " << (suc ? suc->data : -1) << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Two Separate BST Searches

Intuition

1. Search for predecessor: start at root, if curr.data < key, update pre = curr and go right; else go left. 2. Search for successor: start at root, if curr.data > key, update suc = curr and go left; else go right. Both searches take O(H) time and O(1) space, totaling two passes down the tree.

When to apply: When using existing floor and ceil library functions.

Algorithm

  1. Execute two independent searches: one for predecessor (floor of key - 1) and one for successor (ceil of key + 1).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 void findPreSuc(Node* root, Node*& pre, Node*& suc, int key) {
13 pre = nullptr;
14 suc = nullptr;
15
16 // Pass 1: find predecessor
17 Node* curr = root;
18 while (curr) {
19 if (curr->data < key) {
20 pre = curr;
21 curr = curr->right;
22 } else {
23 curr = curr->left;
24 }
25 }
26
27 // Pass 2: find successor
28 curr = root;
29 while (curr) {
30 if (curr->data > key) {
31 suc = curr;
32 curr = curr->left;
33 } else {
34 curr = curr->right;
35 }
36 }
37 }
38};
39
40int main() {
41 Node* root = new Node(50);
42 root->left = new Node(30);
43 root->right = new Node(70);
44 root->left->left = new Node(20);
45 root->left->right = new Node(40);
46 root->right->left = new Node(60);
47 root->right->right = new Node(80);
48
49 Solution sol;
50 Node *pre = nullptr, *suc = nullptr;
51 sol.findPreSuc(root, pre, suc, 65);
52 std::cout << "Pre: " << (pre ? pre->data : -1) << ", Suc: " << (suc ? suc->data : -1) << std::endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(1) auxiliary space

3. Unified Single-Pass Binary Search

Intuition

1. Start curr = root. 2. While curr != null: - If curr.data == key: - If curr.left, pre = max(curr.left). - If curr.right, suc = min(curr.right). - Break loop. - If key < curr.data: suc = curr; curr = curr.left. - If key > curr.data: pre = curr; curr = curr.right. Solves both queries in a single pass in O(H) time and O(1) auxiliary space.

When to apply: Optimal in both time and space. The cleanest single-pass solution.

Algorithm

  1. Descend the tree in a single pass. If key is found, inspect subtrees; otherwise update pre/suc candidates dynamically.

Predecessor and Successor Single-Pass Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
50 is potential predecessor since 50 < 65
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
curr = 50. 65 > 50 -> pre = 50, curr moves right to 70.
Decision / next transition
1
Why this step matters

50 is potential predecessor since 50 < 65.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 void findPreSuc(Node* root, Node*& pre, Node*& suc, int key) {
13 pre = nullptr;
14 suc = nullptr;
15 Node* curr = root;
16
17 while (curr) {
18 if (curr->data == key) {
19 if (curr->left) {
20 Node* p = curr->left;
21 while (p->right) p = p->right;
22 pre = p;
23 }
24 if (curr->right) {
25 Node* s = curr->right;
26 while (s->left) s = s->left;
27 suc = s;
28 }
29 return;
30 } else if (key < curr->data) {
31 suc = curr;
32 curr = curr->left;
33 } else {
34 pre = curr;
35 curr = curr->right;
36 }
37 }
38 }
39};
40
41int main() {
42 Node* root = new Node(50);
43 root->left = new Node(30);
44 root->right = new Node(70);
45 root->left->left = new Node(20);
46 root->left->right = new Node(40);
47 root->right->left = new Node(60);
48 root->right->right = new Node(80);
49
50 Solution sol;
51 Node *pre = nullptr, *suc = nullptr;
52 sol.findPreSuc(root, pre, suc, 65);
53 std::cout << "Pre: " << (pre ? pre->data : -1) << ", Suc: " << (suc ? suc->data : -1) << std::endl;
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Full Inorder Array ScanO(N)O(N)Extract sorted array via inorder traversal, then find the largest element < key and smallest element > key.O(N)
2.Two Separate BST SearchesO(H) where H is tree heightO(1) auxiliary spaceExecute two independent searches: one for predecessor (floor of key - 1) and one for successor (ceil of key + 1).O(H) where H is tree height
3.Unified Single-Pass Binary SearchOptimalO(H) where H is tree heightO(1) auxiliary spaceDescend the tree in a single pass. If key is found, inspect subtrees; otherwise update pre/suc candidates dynamically.O(H) where H is tree height

Common Pitfalls & Crucial Edge Cases

Using `<=` or `>=` instead of strict inequalities

Setting pre to curr when curr.data == key makes a node its own predecessor.

Assuming key is in the tree

Failing when key is absent.

Forgetting to check `curr.left` / `curr.right`

Crashing on null pointers when looking for max of left or min of right.

Crucial Edge Cases to Validate:

  • key equals tree minimum — Predecessor is null, Successor is valid.
  • key equals tree maximum — Predecessor is valid, Successor is null.
  • key does not exist in BST — Returns the floor and ceil nodes surrounding the key.
  • Single node tree — If key matches root, both are null.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State that this problem solves both floor and ceil in a single traversal.
  2. Explain the two cases: when key is found (subtrees have the answers) vs when key is not found (ancestors have the answers).
  3. Highlight the O(1) auxiliary space guarantee.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When the key equals curr.data, where is the in-order predecessor located?

2.What happens if the given key is strictly smaller than the minimum element in the BST?

3.Why does the candidate update pre = curr only occur when key > curr.data?

Back to DSA Sheet