Log inSign up
mediumGeeksforGeeksNot Started

Inorder 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 reference to a node x, find the Inorder Successor of node x in the given BST.

The Inorder Successor of a node x is the node with the smallest key strictly greater than x.data. If no such node exists (i.e. x is the maximum element in the BST), return null.

Constraints:

  • The number of nodes in the BST is in the range [1, 105].
  • 1 <= Node.data <= 105
  • All node values are unique.
  • x is guaranteed to exist in the BST.

What You'll Learn

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

  • Understand the two structural cases of BST inorder successor (right subtree vs ancestor).
  • Unify both cases into a single iterative O(H) binary search loop.
  • Implement the solution in O(1) auxiliary space.

Pattern Recognition Trigger

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

Signals to Look For:

  • Find next greater element in BST.
  • Inorder successor query without parent pointers.
  • BST binary search path tracking.

Algorithmic Decision Tree:

  • If x.val < curr.val: curr could be successor -> succ = curr; curr = curr.left.
  • If x.val >= curr.val: successor must be greater -> curr = curr.right.

Connected Patterns:

Predecessor and Successor in BSTSearch in a Binary Search TreeDelete Node in a BST

1. Inorder Traversal Array Scan

Intuition

Traverse the entire BST using inorder DFS, appending node references into an array. Find index i where arr[i] == x. If i + 1 < arr.length, return arr[i + 1]. Otherwise return null. This takes O(N) time and O(N) space.

When to apply: Baseline brute force when memory and time are unrestricted.

Algorithm

  1. Collect all nodes in an array via full inorder traversal, find node x, and return the next node in the array.
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 Node* inOrderSuccessor(Node* root, Node* x) {
20 std::vector<Node*> nodes;
21 inorder(root, nodes);
22 for (int i = 0; i < (int)nodes.size(); i++) {
23 if (nodes[i] == x) {
24 if (i + 1 < (int)nodes.size()) return nodes[i + 1];
25 return nullptr;
26 }
27 }
28 return nullptr;
29 }
30};
31
32int main() {
33 Node* root = new Node(20);
34 root->left = new Node(8);
35 root->right = new Node(22);
36 root->left->left = new Node(4);
37 root->left->right = new Node(12);
38 root->left->right->left = new Node(10);
39 root->left->right->right = new Node(14);
40
41 Solution sol;
42 Node* succ = sol.inOrderSuccessor(root, root->left); // Successor of 8
43 std::cout << "Successor of 8: " << (succ ? succ->data : -1) << std::endl;
44 return 0;
45}

Time & Space Complexity

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

2. Two-Case Decomposition with Parent Pointers / Min Search

Intuition

Case 1: If x.right != null, the successor is the leftmost node of x.right (while(node.left) node = node.left). Case 2: If x.right == null, start from root and search for x. Whenever moving left, update candidate ancestor succ = curr. Return succ.

When to apply: When explaining the classical textbook breakdown of the successor problem.

Algorithm

  1. If right child exists, find minimum in right subtree; otherwise, search from root to find deepest left ancestor.
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 Node* inOrderSuccessor(Node* root, Node* x) {
13 if (!root || !x) return nullptr;
14
15 // Case 1: x has right subtree
16 if (x->right) {
17 Node* curr = x->right;
18 while (curr->left) curr = curr->left;
19 return curr;
20 }
21
22 // Case 2: x has no right subtree -> deepest ancestor where x is in left subtree
23 Node* succ = nullptr;
24 Node* curr = root;
25 while (curr) {
26 if (x->data < curr->data) {
27 succ = curr;
28 curr = curr->left;
29 } else if (x->data > curr->data) {
30 curr = curr->right;
31 } else {
32 break;
33 }
34 }
35 return succ;
36 }
37};
38
39int main() {
40 Node* root = new Node(20);
41 root->left = new Node(8);
42 root->right = new Node(22);
43 root->left->left = new Node(4);
44 root->left->right = new Node(12);
45 root->left->right->left = new Node(10);
46 root->left->right->right = new Node(14);
47
48 Solution sol;
49 Node* succ = sol.inOrderSuccessor(root, root->left);
50 std::cout << "Successor of 8: " << (succ ? succ->data : -1) << std::endl;
51 return 0;
52}

Time & Space Complexity

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

3. Unified Iterative BST Binary Search

Intuition

Initialize succ = null and curr = root. While curr != null: if x.data < curr.data, curr is strictly greater than x, making it a valid candidate successor. We record succ = curr and search left (curr = curr.left) to find smaller valid candidates. If x.data >= curr.data, curr cannot be the successor, so we move right (curr = curr.right). When curr falls off the tree, succ is guaranteed to be the exact inorder successor. This automatically handles both cases (right child present or absent) in 6 lines of code.

When to apply: The cleanest, most elegant industry standard solution.

Algorithm

  1. Maintain candidate successor in a single while-loop using BST search inequalities.

Approach Execution Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
20 is candidate successor
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
succ = 20
Decision / next transition
Start curr at root 20
Why this step matters

20 is candidate successor.

Step 1 / 5
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 Node* inOrderSuccessor(Node* root, Node* x) {
13 Node* succ = nullptr;
14 Node* curr = root;
15
16 while (curr) {
17 if (x->data < curr->data) {
18 succ = curr; // curr is a candidate successor
19 curr = curr->left; // look for a smaller candidate
20 } else {
21 curr = curr->right;// curr cannot be successor, search right
22 }
23 }
24
25 return succ;
26 }
27};
28
29int main() {
30 Node* root = new Node(20);
31 root->left = new Node(8);
32 root->right = new Node(22);
33 root->left->left = new Node(4);
34 root->left->right = new Node(12);
35 root->left->right->left = new Node(10);
36 root->left->right->right = new Node(14);
37
38 Solution sol;
39 Node* succ = sol.inOrderSuccessor(root, root->left); // Node 8
40 std::cout << "Successor of 8: " << (succ ? succ->data : -1) << std::endl;
41 return 0;
42}

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.Inorder Traversal Array ScanO(N)O(N)Collect all nodes in an array via full inorder traversal, find node x, and return the next node in the array.O(N)
2.Two-Case Decomposition with Parent Pointers / Min SearchO(H) where H is tree heightO(1) auxiliary spaceIf right child exists, find minimum in right subtree; otherwise, search from root to find deepest left ancestor.O(H) where H is tree height
3.Unified Iterative BST Binary SearchOptimalO(H) where H is tree heightO(1) auxiliary spaceMaintain candidate successor in a single while-loop using BST search inequalities.O(H) where H is tree height

Common Pitfalls & Crucial Edge Cases

Checking `x.data <= curr.data`

If equal, setting succ = curr makes the node its own successor!

Searching the whole tree

Using standard O(N) binary tree traversal instead of O(H) BST directed search.

Assuming right child always exists

Fails on leaf nodes whose successor is an ancestor.

Crucial Edge Cases to Validate:

  • x is the maximum node in the tree — Traversal ends with succ == null, correctly returning null.
  • x is a leaf node with an ancestor successor — Successfully captures the deepest parent where x was in the left subtree.
  • x is the root node with a right subtree — Successor is the minimum node of the right subtree.
  • Single node tree — Successor is null.

Interview Tips & Best Practices

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

  1. State both cases first to show structural understanding: right-child min vs ancestor.
  2. Then showcase mastery by presenting the Unified 6-line BST binary search loop.
  3. Emphasize O(1) auxiliary space and O(H) runtime.

Quick Comprehension Check

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

1.When does a node in a BST have NO inorder successor?

2.Why does the condition if (x.data < curr.data) correctly identify a candidate successor?

3.What is the worst-case time complexity of finding the inorder successor in an unbalanced BST?

Back to DSA Sheet