Leetcode #510: Inorder Successor in BST II
In this guide, we solve Leetcode #510 Inorder Successor in BST II in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.
Quick Facts
- Difficulty: Medium
- Premium: Yes
- Tags: Tree, Binary Search Tree, Binary Tree
Intuition
The input is a tree, so recursive decomposition is a natural fit.
We can compute the answer by combining results from left and right subtrees.
Approach
Use DFS and pass the required state through recursive calls.
Combine child results to compute the answer for each node.
Steps:
- Pick traversal order.
- Recurse with state.
- Combine results from children.
Example
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
Python Solution
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
if node.right:
node = node.right
while node.left:
node = node.left
return node
while node.parent and node.parent.right is node:
node = node.parent
return node.parent
Complexity
The time complexity is , where is the height of the binary tree. The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.