Introduction

The Inorder Successor in BST problem is one of the most important Binary Search Tree interview questions asked in coding interviews and online coding platforms like GeeksforGeeks.

This problem tests your understanding of:

1. Binary Search Tree properties
2. Inorder traversal
3. Recursive searching
4. Tree optimization techniques
5. Successor logic in BST

Understanding this problem properly helps in solving many advanced BST questions efficiently.

Problem Link

🔗 GeeksforGeeks – Inorder Successor in BST

Problem Statement

Given:

1. A Binary Search Tree
2. A reference node k

Find the:

of that node.

What is Inorder Successor?

The inorder successor of a node is:

The next greater node in the inorder traversal of the BST.

Example 1

Input

Inorder Traversal

Output

Example 2

Input

Inorder Traversal

Output

Key BST Observation

In a BST:

The inorder traversal of BST is always:

This property helps us optimize the search.

Intuition

Suppose:

and current node is:

Since:

this node can potentially be the inorder successor.

But there may exist a smaller valid successor in the left subtree.

So:

1. Store current node as possible answer
2. Move left

Brute Force Approach

Idea

1. Perform inorder traversal
2. Store traversal in list
3. Find node k
4. Return next element

Brute Force Java Solution

Brute Force Complexity

Time Complexity

Space Complexity

because of traversal list.

Optimized BST Approach

Instead of traversing the entire tree:

1. Use BST properties
2. Reduce unnecessary traversal
3. Search efficiently

Optimized Java Solution

How This Solution Works

Whenever:

the current node becomes a possible successor candidate.

But there may exist a smaller valid successor in the left subtree.

So:

1. Store current node
2. Move left

Why Move Right Otherwise?

If:

then current node cannot be successor.

Move right to search for larger values.

Dry Run

Input

Step 1

Current node:

Since:

possible successor:

Move left.

Step 2

Current node:

Since:

Move right.

Step 3

Current node:

Since:

update successor:

Move left.

Step 4

Current node:

Since:

update successor:

Move left.

Step 5

Node becomes null.

Return:

Final Answer

Alternative Inorder Traversal Approach

Another common approach:

1. Perform inorder traversal
2. Track previous node
3. When previous node becomes k, current node is successor

Alternative Recursive Solution

Time Complexity Analysis

Optimized BST Solution

Best Case

Balanced BST.

Worst Case

Skewed BST.

Space Complexity

Recursive Stack

where:

Interview Explanation

In interviews explain:

Whenever we encounter a node greater than k, it becomes a possible inorder successor candidate. Then we move left to search for a smaller valid successor.

This demonstrates:

1. BST optimization understanding
2. Recursive traversal logic
3. Efficient searching skills

Common Mistakes

1. Traversing Entire Tree Unnecessarily

BST property already reduces search space.

2. Returning First Greater Node

Need the:

not any greater node.

3. Forgetting Candidate Update

Always update candidate before moving left.

4. Confusing Floor/Ceil Logic

Successor logic is different from:

1. Floor
2. Ceil
3. Predecessor

FAQs

Q1. What is inorder successor?

The next greater node in inorder traversal.

Q2. Why BST helps optimization?

BST ordering allows skipping unnecessary branches.

Q3. Can inorder successor be absent?

Yes.

If node is largest element, answer is:

Q4. Can this be solved iteratively?

Yes.

Iterative solution is also common in interviews.

Related BST Problems

Practice these next:

1. Search in BST
2. Ceil in BST
3. Floor in BST
4. Validate BST
5. Lowest Common Ancestor in BST
6. Kth Smallest Element in BST

Conclusion

Inorder Successor in BST is a very important interview problem because it teaches:

1. BST optimization
2. Recursive searching
3. Successor logic
4. Tree traversal efficiency

The key idea is:

Whenever a node is greater than k, it becomes a possible successor candidate, but a smaller valid successor may still exist in the left subtree.

Mastering this logic makes advanced BST problems significantly easier.