Recover Binary Search Tree

The tree keeps its shape. The inorder sequence gives away the crime.

A binary search tree has a structural invariant that is more useful than its parent-child relationships: inorder traversal visits values in sorted order. If exactly two node values were exchanged, the fastest route to recovery is to stream that traversal, find the ordering violations, and swap the two misplaced values back.

The tree links never move. Only first.val and second.val change.

The contract and the answer direction

The repair has four constraints:

• Exactly two node values were swapped.
• The tree structure is still the original structure.
• Child pointers must remain unchanged.
• Recovery happens in place; the function returns nothing.

The solution direction is:

1. Traverse the tree in inorder.
2. Compare each visited node with the previously visited node.
3. When current.val < previous.val, record an inversion.
4. At the first inversion, save previous as the first misplaced node.
5. At every inversion, update second to current.
6. After traversal, swap first.val and second.val.

For ordinary recursive DFS, this takes O(n) time and O(h) auxiliary space, where h is the tree height. The constant-space follow-up replaces the traversal mechanism with Morris traversal; the candidate-selection logic stays the same.

The key decision is simple:

Repair the ordered value stream, not the tree topology.

Trying to identify the bad nodes from local parent-child relationships creates unnecessary cases. A misplaced value can still have locally plausible children. Inorder gives us the global ordering signal directly.

Find the BST signal in inorder

Assume the usual left-node-right inorder mechanics. The important fact here is what that order certifies:

For a valid BST under the problem's distinct-value ordering convention, inorder values appear in strictly increasing order.

Suppose the valid sequence is:

[1, 2, 3, 4, 5]

If two values are swapped, the observed sequence may become:

[1, 3, 2, 4, 5]

The adjacent pair 3, 2 is out of order. Call this an inversion: the current value is smaller than the value immediately before it.

A non-adjacent swap may produce:

[1, 4, 3, 2, 5]

Now there are two inversions:

4 > 3
3 > 2

The tree itself has not changed. The traversal exposes a damaged sorted sequence.

This is a reusable DFS pattern: when a traversal produces a constrained sequence, scan local violations while carrying only the state needed to compare neighboring observations. You do not need to materialize the entire sequence unless the simpler baseline is useful for explanation.

Derive the candidate state

Each state variable should answer one concrete obligation.

previous

previous is the last node visited in inorder. It lets us compare the current node with its immediate predecessor:

if previous and previous.val > node.val:
    ...

The comparison belongs between the left and right recursive calls. That is the point at which the current node is being processed in inorder order.

first

At the first inversion, previous holds the larger misplaced value. Save that node once:

first = previous

For [1, 3, 2, 4], the first inversion is 3 > 2, so first becomes the node containing 3.

second

At every inversion, the current node is a candidate for the smaller misplaced value:

second = node

This update rule handles both corruption shapes.

For adjacent swaps:

[1, 3, 2, 4]

There is one inversion. We record:

first = 3
second = 2

For separated swaps:

[1, 4, 3, 2, 5]

The state changes like this:

first must remain 4; second must move to 2.

That is why the rules are asymmetric:

• Set first only at the first inversion.
• Set second at every inversion.

Store node references, not just values or inorder indices. The required operation is to mutate the existing node objects while preserving every link.

Baseline, then the smaller state machine

A straightforward baseline is to materialize the inorder nodes:

1. Traverse inorder and store node references.
2. Scan the resulting list for inversions.
3. Identify first and second.
4. Swap their values.

This is easy to inspect, but the list costs O(n) auxiliary space.

Sorting the values and rebuilding the tree is a worse fit. It performs more work than necessary and obscures the contract: the problem says two values were swapped, not that the structure should be reconstructed. Rebuilding can also violate the requirement that the original node links remain unchanged.

The optimized version streams the same sequence. It keeps only:

• the previous visited node,
• the first misplaced node,
• the latest inversion's current node.

That is the entire state machine. No inorder array. No sorting. No tree reconstruction.

In an interview, I would derive the array version first if it makes the invariant obvious, then remove the array by asking: What information from the past do I actually use? The answer is only the predecessor and the two candidate references.

Why the swap repairs the tree

Model the valid inorder values as a sorted sequence:

a[0] < a[1] < ... < a[n - 1]

Two positions i < j have had their values exchanged. The larger value from position j appears too early, and the smaller value from position i appears too late.

Adjacent swapped positions

If j = i + 1, the values are next to each other. The sequence contains one inversion:

... larger, smaller ...

The first inversion identifies the larger value as first and the smaller value as second.

Separated swapped positions

If j > i + 1, the larger value appears before several values that should precede it. That creates the first inversion. The smaller value appears later and creates the final inversion.

The first inversion identifies the larger misplaced node:

first = previous

The last inversion identifies the smaller misplaced node:

second = current

After exchanging first.val and second.val, the inorder values return to their original sorted order. Since the child links never changed, the tree's structure is the same and its ordering invariant is restored.

The proof is independent of the traversal implementation. Recursive DFS, an explicit stack, and Morris traversal all work if they expose nodes in the same inorder sequence and apply the same inversion rules.

Recursive Python implementation

Here is a complete recover BST Python solution using recursive DFS. It mutates the supplied tree and returns None.

from typing import Optional


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(
#         self,
#         val: int = 0,
#         left: Optional["TreeNode"] = None,
#         right: Optional["TreeNode"] = None,
#     ):
#         self.val = val
#         self.left = left
#         self.right = right


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

        def inorder(node: Optional["TreeNode"]) -> None:
            nonlocal previous, first, second

            if node is None:
                return

            inorder(node.left)

            if previous is not None and previous.val > node.val:
                if first is None:
                    first = previous
                second = node

            previous = node
            inorder(node.right)

        inorder(root)

        if first is not None and second is not None:
            first.val, second.val = second.val, first.val

The code follows the derivation directly:

• previous advances after the current node is processed.
• The comparison occurs after the left subtree and before the right subtree.
• first is assigned only once.
• second is updated for every BST inorder violation.
• The value swap waits until the traversal has found the full pair.

The final guard is defensive. Under the stated contract, exactly two values were swapped, so both references should exist. The guard prevents an accidental attribute error if the method is reused with an invalid or already-correct input.

Do not swap during traversal. At the first inversion, you know one endpoint, but a separated swap may produce a later inversion that changes second. The repair belongs after discovery.

Dry-run the state transitions

Adjacent swap

Consider the inorder sequence:

[1, 3, 2, 4]

The traversal state evolves as follows:

The final swap changes 3, 2 to 2, 3:

[1, 2, 3, 4]

Separated swap

Now consider:

[1, 4, 3, 2, 5]

The algorithm swaps 4 and 2, producing the sorted inorder sequence:

[1, 2, 3, 4, 5]

Several plausible implementations fail here:

• Swap immediately at the first violation: works for adjacent swaps, but can repair the wrong pair for separated swaps.
• Stop after the first violation: misses the later endpoint.
• Store only values: makes it harder to express the in-place node mutation and can lead to unnecessary searches.
• Compare against an ancestor: the relevant predecessor is the previous inorder node, which may be far away in the tree.
• Set first at every violation: overwrites the larger endpoint and loses the original candidate.

Read the error. Trace the state. Fix the assumption. The second dry run is where the algorithm earns its place.

Meet the O(1)-space follow-up

Recursive DFS uses the call stack. An explicit stack uses a data structure to remember the path toward the next inorder node. Both require O(h) auxiliary space.

The follow-up asks whether the traversal can use O(1) auxiliary space. Morris inorder traversal answers that by temporarily threading the tree: when a node has a left subtree, find its inorder predecessor and temporarily point that predecessor's right pointer back to the current node.

This changes how traversal state is stored, not how corrupted values are detected.

The Morris version still maintains:

• previous,
• first,
• second.

It still checks:

previous.val > current.val

It still records first once and updates second at every inversion.

The operational obligations are stricter, though:

1. If the current node has no left child, process it and move right.
2. If it has a left child, find its inorder predecessor.
3. If the predecessor's right pointer is empty, create the temporary thread and move left.
4. If the predecessor already points to the current node, remove the thread, process the current node, and move right.
5. Restore every temporary pointer before finishing.

That restoration step is part of correctness. Claiming constant space while leaving threads in the tree is not a valid implementation; it changes the input structure and can create cycles or corrupt later operations.

Morris traversal processes each link a constant number of times, so the total time remains O(n), with O(1) auxiliary space when all temporary links are restored. It is a genuine constant-space tree traversal, but it has more control-flow and pointer-rewiring failure modes than the recursive version.

My interview rule is practical: derive the invariant with recursion or an explicit stack first. Use Morris when the interviewer explicitly requires constant extra space or asks for the follow-up. Do not introduce pointer threading before you can explain which inorder event triggers each comparison.

Complexity, edge cases, and submission checks

For the recursive implementation:

• Time: O(n). Each node is visited once, and each visit performs constant-time state updates.
• Auxiliary space: O(h). The recursion depth equals the tree height.
• Worst-shaped tree: A skewed tree can have h = n, so the auxiliary space can become O(n).

For Morris traversal:

• Time: O(n).
• Auxiliary space: O(1), provided temporary links are always removed.

Check these cases before submitting:

• A two-node tree whose values are swapped.
• Adjacent swapped values, producing one inversion.
• Separated swapped values, producing two inversions.
• A left-skewed or right-skewed tree.
• A null root if the method is written defensively.
• The smallest valid input, which has exactly two nodes.
• A tree where the first inversion occurs early and the second occurs near the end.

Then verify the implementation contract:

• Only val fields change.
• No left or right pointer changes.
• The function returns None.
• first is assigned only on the first inversion.
• second is assigned on every inversion.
• previous advances after every processed node.
• The final swap happens after traversal.
• Morris threads, if used, are fully restored.

The broader recognition rule is worth carrying into other problems: when a structured object has a traversal that exposes a globally ordered sequence, inspect local violations in that sequence before changing the structure. Write the predecessor state, trace one inversion, and let the invariant choose the algorithm. Use recursion or a stack for clarity; reach for Morris only when constant auxiliary space is truly part of the requirement.