NeetCode #468LC-510MediumTrees
← Back to All Problems#468 · #510 · Inorder Successor in BST II(二叉搜索树中的中序后继 II)
📌 Problem Statement & Constraints
Given a node in a binary search tree where every node has a
parent pointer, return its in-order successor (the next node in the in-order traversal), or None if it does not exist. Constraints: the number of nodes is in [1, 10^4], all values are distinct.💡 Core Algorithmic Approaches
- If the node has a right subtree, the successor is the leftmost node of that right subtree.
- Otherwise, walk up via the parent pointers until you arrive from a left child -- that parent is the successor.
- If you reach the root without ever arriving from a left child, there is no successor.
- Both cases are O(h), and no traversal of the whole tree is needed.
💻 Benchmark Python3 Implementation
class Solution:
def inorderSuccessor(self, node: "Node") -> "Optional[Node]":
# case 1: a right subtree exists -> leftmost node of it
if node.right:
cur = node.right
while cur.left:
cur = cur.left
return cur
# case 2: go up until we come from a left child
cur = node
while cur.parent and cur.parent.right is cur:
cur = cur.parent
return cur.parent # None if we reached the root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(h): at most one descent plus one ascent.
💾 Space Complexity
O(1): no recursion or extra structures.
⚠️ Interview Pitfalls & Follow-ups
- Returning
node.rightdirectly: the successor is the leftmost node of the right subtree, not its root. - Walking up unconditionally: the walk must stop at the first ancestor from which we arrived via a left child.
- Using a full in-order traversal: O(n) when O(h) suffices, and the parent pointers make the traversal unnecessary.
- Forgetting the no-successor case: the maximum node has none, and the loop leaves
cur.parentasNone.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.