LeetCode 285: Inorder Successor in BST Solution
Master LeetCode problem 285 (Inorder Successor in BST), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
285. Inorder Successor in BST
Problem Explanation
Explanation
To find the inorder successor in a BST, we can follow these steps:
- If the right child of the current node is not null, then the successor is the leftmost node in the right subtree.
- If the right child of the current node is null, then we need to backtrack to find the successor. We keep track of the potential successor as we traverse the tree.
- When we find the target node, if its right child is not null, then the successor is the leftmost node in the right subtree of the target node. Otherwise, the potential successor stored while traversing is the actual successor.
Time complexity: O(h), where h is the height of the BST. Space complexity: O(1) if not considering the recursion stack.
Solution Code
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode successor = null;
while (root != null) {
if (root.val > p.val) {
successor = root;
root = root.left;
} else {
root = root.right;
}
}
return successor;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 285 (Inorder Successor in BST)?
This page provides optimized solutions for LeetCode problem 285 (Inorder Successor in BST) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 285 (Inorder Successor in BST)?
The time complexity for LeetCode 285 (Inorder Successor in BST) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 285 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 285 in Java, C++, or Python.