Skip to main content
Talentd

Inorder Successor in BST - Solution & Explanation

MediumPremiumFree on FleetCodeTreeDepth-First SearchBinary Search TreeBinary Tree9 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.

The successor of a node p is the node with the smallest key greater than p.val.

 

Example 1:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -105 <= Node.val <= 105
  • All Nodes will have unique values.

Approach Overview

Problem Overview: Given the root of a Binary Search Tree and a node p, return the node that appears immediately after p in an inorder traversal. The inorder successor is the smallest value strictly greater than p.val.

Approach 1: Inorder Traversal (DFS) (Time: O(n), Space: O(n))

The straightforward solution performs a full inorder traversal of the tree using depth-first search. Inorder traversal of a binary search tree produces values in sorted order. Store nodes in a list while traversing left → root → right. Once traversal completes, iterate through the list to find node p and return the next element. This approach is simple and works for any binary tree, but it uses extra memory to store all nodes and always scans the entire tree even when the successor is near the root.

Approach 2: Binary Search Using BST Property (Time: O(h), Space: O(1))

A Binary Search Tree gives a stronger guarantee: left subtree values are smaller than the node, and right subtree values are larger. Use this ordering to search for the successor without traversing every node. Start at the root and keep a candidate successor. If p.val is smaller than the current node's value, the current node could be the successor, so store it and move left to find a smaller valid candidate. If p.val is greater than or equal to the current node's value, move right since any successor must be larger. Continue until reaching a null node. The stored candidate is the inorder successor.

This approach effectively performs a guided binary search through the BST. The runtime depends on the tree height h, which is O(log n) for balanced trees and O(n) in the worst case of a skewed tree. It avoids extra memory because it only keeps a pointer to the best candidate seen so far.

Recommended for interviews: Interviewers typically expect the BST binary search approach. Starting with the inorder traversal shows you understand what “inorder successor” means, but the optimized solution demonstrates that you can leverage the structural guarantees of a Binary Search Tree to reduce the search to O(h) time with constant space.

Solution

The in-order traversal of a binary search tree is an ascending sequence, so we can use the binary search method.

The in-order successor node of a binary search tree node p satisfies:

  1. The value of the in-order successor node is greater than the value of node p.
  2. The in-order successor is the node with the smallest value among all nodes greater than p.

Therefore, for the current node root, if root.val > p.val, then root could be the in-order successor of p. We record root as ans and then search the left subtree, i.e., root = root.left. If root.val leq p.val, then root cannot be the in-order successor of p, and we search the right subtree, i.e., root = root.right.

The time complexity is O(h), where h is the height of the binary search tree. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Inorder Traversal (DFS)O(n)O(n)Simple baseline approach or when BST properties are not leveraged
Binary Search Using BST PropertyO(h)O(1)Optimal solution for Binary Search Trees; efficient when tree height is small

Video Solution

INORDER SUCCESSOR IN BST | PYTHON | LEETCODE 285 • Cracking FAANG • 7,329 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Inorder Successor in BST easy or hard?
The problem is generally classified as Medium difficulty. Understanding inorder traversal is straightforward, but recognizing how to exploit BST ordering to achieve an O(h) solution is the key interview insight.
How to solve Inorder Successor in BST in O(h)?
Start from the root and compare p.val with the current node. If p.val is smaller, store the current node as a potential successor and move left. If p.val is greater or equal, move right. Continue until reaching null, and the stored candidate will be the inorder successor.
Inorder Successor in BST Python or Java solution
Most implementations follow the same BST search pattern in Python, Java, C++, or other languages. Maintain a variable for the successor while traversing from the root and update it whenever you encounter a node with value greater than p.val before moving left.
What is the best approach for Inorder Successor in BST?
The best approach uses the Binary Search Tree property to perform a guided search. Traverse from the root while tracking a candidate successor whenever the current node value is greater than p.val. This runs in O(h) time where h is the height of the tree and uses O(1) extra space.
What data structure is used in Inorder Successor in BST?
The problem is based on the Binary Search Tree data structure. Solutions typically combine BST ordering with traversal techniques such as Depth-First Search or binary search-style navigation through the tree.
What is the time complexity of Inorder Successor in BST?
The optimal solution runs in O(h) time where h is the height of the Binary Search Tree. In balanced trees this becomes O(log n), while in the worst case of a skewed tree it can degrade to O(n). Space complexity is O(1) because no additional data structures are required.
Is Inorder Successor in BST asked at Google Amazon or Meta?
Inorder successor problems frequently appear in interviews at companies like Amazon, Google, and Meta because they test understanding of Binary Search Trees and traversal logic. Variants may ask for successor with parent pointers or require handling multiple queries efficiently.

Ready to solve this problem?

Practice Inorder Successor in BST with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Search Tree Iterator

Next

Binary Tree Inorder Traversal