Basic example
Input
root = TreeNode(20, TreeNode(10, TreeNode(5), TreeNode(15)), TreeNode(30)); p_val = 15
Output
20
The inorder traversal is [5,10,15,20,30]; successor of 15 is 20.
Full lesson preview
Find the inorder successor in a BST
Given the root of a Binary Search Tree (BST) and a target value p, find the inorder successor of the node with value p.
Python practice16 minTrees & Binary TreesIntermediateLast updated March 29, 2026
Problem statement
You are given the root of a Binary Search Tree (BST) and an integer p_val representing the value of a node in the tree. The inorder successor of a node in a BST is the node with the smallest key greater than the node's key. Return the value of the inorder successor node if it exists; otherwise return None.
Notes:
- The input p_val may or may not exist in the tree. If p_val is not found, return None.
- You should leverage BST properties to achieve an efficient solution (expected O(h) time, where h is the tree height).
Task
Implement a function that returns the inorder successor's value in a BST (or None if no successor exists).
Examples
Input format
A BST constructed using TreeNode(val, left, right) and an integer p_val.
Output format
Return the integer value of the inorder successor, or None if no successor exists.
Constraints
- The tree node values are integers and unique per BST property.
- Aim for O(h) time and O(1) extra space (excluding recursion stack if used).
- Tree height h can be up to the number of nodes in the worst case.
Samples
Sample 1
Input
TreeNode(20, TreeNode(10, TreeNode(5), TreeNode(15)), TreeNode(30)), 10
Output
15
Successor of 10 is 15.