⚡Flashcard Drill➔
NeetCode #444LC-99MediumTrees
← Back to All Problems

#444 · #99 · Recover Binary Search Tree(恢复二叉搜索树)

📌 Problem Statement & Constraints

You are given the root of a binary search tree in which exactly two nodes were swapped by mistake. Recover the tree without changing its structure. Constraints: the number of nodes is in [2, 1000], -2^31 <= Node.val <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. An in-order traversal of a valid BST is strictly increasing, so the two swapped nodes appear as inversions in the traversal.
  2. Track the previous node; when prev.val > node.val, an inversion has been found.
  3. The first inversion's prev is the first misplaced node, and the last inversion's node is the second.
  4. Swapping their values restores the BST. This works for both adjacent and non-adjacent swaps.

💻 Benchmark Python3 Implementation

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        self.first = None
        self.second = None
        self.prev = None

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left)
            if self.prev and self.prev.val > node.val:
                # the first inversion gives the larger node, the last gives the smaller
                if self.first is None:
                    self.first = self.prev
                self.second = node
            self.prev = node
            inorder(node.right)

        inorder(root)
        self.first.val, self.second.val = self.second.val, self.first.val

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one in-order traversal.
💾 Space Complexity
O(h) for the recursion stack. Morris traversal would give O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Swapping as soon as an inversion is found: for a non-adjacent swap there are two inversions, and the correct pair is the first inversion's larger node and the last inversion's smaller node.
  • Assuming the swapped nodes are adjacent in value: they need not be.
  • Comparing only adjacent values without tracking first and second separately: both positions must be recorded.
  • Rebuilding the tree: the values are swapped in place, leaving the structure untouched.
⚡
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