LeetCode 99: Recover Binary Search Tree Solution in Python Explained

Problem Statement

In LeetCode 99, you’re given the root of a BST where exactly two nodes have been swapped, breaking the BST property (left < root < right). Your task is to recover the tree by swapping their values in-place, without changing the structure. This builds on validation from LeetCode 98: Validate Binary Search Tree, shifting focus to correction.

Constraints

• Number of nodes: 2 <= n <= 10^5
• Node values: -2^31 <= Node.val <= 2^31 - 1

Example

Let’s see some cases:

Copy codeInput: root = [1,3,null,null,2]
      1
     /
    3
   /
  2
Output: [3,1,null,null,2]
      3
     /
    1
   /
  2
Explanation: 1 and 3 swapped, fix by swapping back.

Copy codeInput: root = [3,1,4,null,null,2]
      3
     / \
    1   4
       /
      2
Output: [2,1,4,null,null,3]
      2
     / \
    1   4
       /
      3
Explanation: 2 and 3 swapped, restore BST.

Copy codeInput: root = [2,1,3]
Output: [2,1,3]
Explanation: Already valid, but constraint ensures two nodes swapped (hypothetical case).

These examples show we’re correcting two swapped nodes.

Understanding the Problem

How do you solve LeetCode 99: Recover Binary Search Tree in Python? Take root = [1,3,null,null,2]. Inorder should be [1,2,3], but it’s [2,3,1]—1 and 3 are swapped. We need to swap them back to [3,1,null,null,2]. This isn’t a string task like LeetCode 97: Interleaving String; it’s about BST repair. We’ll use: 1. Inorder Traversal with Swap: O(n) time, O(h) space—our best solution. 2. Morris Traversal: O(n) time, O(1) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Inorder Traversal with Swap Approach (Primary)

Explanation

Inorder Traversal with Swap uses the BST property that inorder traversal (left, root, right) yields a sorted sequence. Traverse the tree, track the previous node, and identify two violations (where a node isn’t greater than its predecessor). Swap the first and last violators’ values. It’s the best solution due to its simplicity, efficiency, and intuitive use of inorder properties.

For [1,3,null,null,2]:

• Inorder: [2,3,1].
• Violations: 2 > 3 (first), 3 > 1 (second).
• Swap 1 and 3 → [3,1,null,null,2].

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: root = [1,3,null,null,2]

Goal: Modify to [3,1,null,null,2].

• Start: prev = None, first = None, second = None.
• Step 1: Inorder traversal.
• Left: None, skip.
• Root 1: No prev, set prev = 1.
• Right: Traverse 3.
• Step 2: Node 3.
• Left: Traverse 2.
• Step 3: Node 2.
• prev = 1, 2 > 1, no violation yet, prev = 2.
• Back to 3.
• Step 4: Node 3.
• prev = 2, 3 > 2, but 2,3,1 shows violation later, prev = 3.
• Step 5: Backtrack to 1, then root’s right done.
• Step 6: Re-traverse with logic.
• 2 > 3: first = 2, second = 3.
• 3 > 1: Update second = 1.
• Step 7: Swap first.val = 2 and second.val = 1 → [3,1,null,null,2].
• Finish: Tree corrected.

Example 2: root = [3,1,4,null,null,2]

Goal: Modify to [2,1,4,null,null,3].

• Start: Inorder: [1,3,2,4].
• Step 1: 1, prev = 1.
• Step 2: 3 > 1, prev = 3.
• Step 3: 2 < 3, first = 3, second = 2.
• Step 4: 4 > 2, prev = 4.
• Step 5: Swap 3 and 2 → [2,1,4,null,null,3].
• Finish: Tree corrected.

Example 3: root = [2,1]

Goal: Modify to [2,1] (assuming swap, e.g., [1,2] to [2,1]).

• Start: Inorder: [1,2].
• Step: No violations, but constraint assumes swap (hypothetical).
• Finish: [2,1] (already valid or swapped).

How the Code Works (Inorder Traversal with Swap) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def recoverTree(root: TreeNode) -> None:
    # Line 1: Initialize pointers as lists for mutability
    prev = [None]
    first = [None]
    second = [None]
    # Lists allow modification in recursive scope (e.g., prev tracks last visited)

    # Line 2: Define inorder traversal helper
    def inorder(node: TreeNode):
        # node = current node in traversal (e.g., root=1)

        # Line 3: Base case - empty node
        if not node:
            # If node is None (e.g., left of 1), skip
            return

        # Line 4: Traverse left subtree
        inorder(node.left)
        # Visits left child first (e.g., None for root=1)

        # Line 5: Check for violation with previous node
        if prev[0] and node.val < prev[0].val:
            # If prev exists and current value is less (e.g., 2 < 3 in [2,3,1])
            # Indicates a swap occurred

            # Line 6: Set first violation
            if not first[0]:
                first[0] = prev[0]
                # First node of pair (e.g., 3 in [2,3,1])

            # Line 7: Set second violation
            second[0] = node
            # Second node of pair (e.g., 1 in [2,3,1], updates from 3)

        # Line 8: Update prev to current node
        prev[0] = node
        # Sets prev for next comparison (e.g., from 2 to 3)

        # Line 9: Traverse right subtree
        inorder(node.right)
        # Visits right child (e.g., 2 for root=1)

    # Line 10: Perform inorder traversal
    inorder(root)
    # Starts traversal from root (e.g., 1)
    # Identifies swapped nodes

    # Line 11: Swap values of first and second nodes
    first[0].val, second[0].val = second[0].val, first[0].val
    # Swaps values in-place (e.g., 1 ↔ 3)
    # Corrects the BST without returning

This detailed breakdown clarifies how inorder traversal identifies and fixes the swapped nodes efficiently.

Alternative: Morris Traversal Approach

Explanation

Morris Traversal modifies the tree temporarily to traverse inorder without recursion or a stack, identifying swapped nodes similarly. It restores the tree afterward, using O(1) space. It’s a space-efficient alternative, leveraging threading to avoid extra memory.

For [1,3,null,null,2]:

• Inorder: [2,3,1].
• Find 3 > 1, swap 1 and 3.

Step-by-Step Example (Alternative)

For [1,3,null,null,2]:

• Start: prev = None, first = None, second = None, curr = 1.
• Step 1: No left, visit 1, prev = 1.
• Step 2: Right 3, left 2, thread 2.right = 3, visit 2.
• 2 > 1, prev = 2.
• Step 3: Visit 3, 3 > 2, but 2 < 3, first = 2.
• Step 4: 1 < 3, second = 1.
• Step 5: Swap 2 and 1 → [3,1,null,null,2].
• Finish: Tree corrected.

How the Code Works (Morris Traversal)

Copy codedef recoverTreeMorris(root: TreeNode) -> None:
    curr = root
    prev = None
    first = None
    second = None

    while curr:
        if not curr.left:
            if prev and curr.val < prev.val:
                if not first:
                    first = prev
                second = curr
            prev = curr
            curr = curr.right
        else:
            pred = curr.left
            while pred.right and pred.right != curr:
                pred = pred.right
            if not pred.right:
                pred.right = curr
                curr = curr.left
            else:
                pred.right = None
                if prev and curr.val < prev.val:
                    if not first:
                        first = prev
                    second = curr
                prev = curr
                curr = curr.right

    first.val, second.val = second.val, first.val

Complexity

• Inorder Traversal with Swap:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Morris Traversal:
• Time: O(n) – visits each node once.
• Space: O(1) – no extra space.

Efficiency Notes

Inorder Traversal with Swap is the best solution with O(n) time and O(h) space, offering simplicity and clarity—Morris Traversal matches time complexity with O(1) space, making it a strong alternative when memory is critical.

Key Insights

• Inorder: Detects swaps via order.
• Two Nodes: Exactly two violations.
• In-Place: Modifies values directly.

Additional Example

For root = [4,2,6,1,3,5,7]:

• Goal: Swap 4 and 2 → [2,1,4,null,null,3,6,null,null,5,7].
• Inorder: [1,4,3,2,5,6,7], swap 4 and 2.

Edge Cases

• Two Nodes: [2,1] → [1,2].
• Full Swap: [3,1] → [1,3].
• Large Values: [2^31-1,1] → [1,2^31-1].

Both solutions handle these well.

Final Thoughts

LeetCode 99: Recover Binary Search Tree in Python is a clever BST repair challenge. The Inorder Traversal with Swap solution stands out for its efficiency and ease, while Morris Traversal offers a space-saving twist. Want more? Try LeetCode 98: Validate Binary Search Tree for validation or LeetCode 94: Binary Tree Inorder Traversal for traversal basics. Ready to practice? Solve LeetCode 99 on LeetCode with [1,3,null,null,2], aiming to recover [3,1,null,null,2]—test your skills now!