⚡Flashcard Drill➔
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

  1. If the node has a right subtree, the successor is the leftmost node of that right subtree.
  2. Otherwise, walk up via the parent pointers until you arrive from a left child -- that parent is the successor.
  3. If you reach the root without ever arriving from a left child, there is no successor.
  4. 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.right directly: 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.parent as None.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems