Inorder Successor in BST
Medium · Graphs · Explanation and code example
BST Successor Search
How it works
The successor is the smallest value strictly greater than p.val. A root no greater than p cannot qualify, so search its right subtree. Otherwise search left for a closer candidate and fall back to the root if none exists.
Steps
- Compare each root with p.val.
- Search right when root.val <= p.val.
- Otherwise return a successor found on the left, or the root.
Complexity
- Time: O(h), where h is tree height.
- Space: O(h) recursive stack.
Things to watch for
- The successor need not be a descendant of p.
- The largest node has no successor.
- A successor must be strictly greater.
Python code example
class Solution:
def inorderSuccessor(
self,
root: TreeNode | None,
p: TreeNode | None,
) -> TreeNode | None:
if not root:
return None
if root.val <= p.val:
return self.inorderSuccessor(root.right, p)
return self.inorderSuccessor(root.left, p) or root
C++ code example
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if (root == nullptr)
return nullptr;
if (root->val <= p->val)
return inorderSuccessor(root->right, p);
TreeNode* left = inorderSuccessor(root->left, p);
return left ? left : root;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.