Generated by Codex with GPT-5

Quick facts

Problem gist

A binary search tree should produce values in sorted order when walked with inorder traversal: left subtree, current node, then right subtree. In this problem, exactly two node values were swapped by mistake. The tree shape is still the same, but the values break the BST ordering rule.

The task is to repair the tree in place without changing its structure. That means the right fix is not to rebuild the tree or move nodes around. The right fix is to identify the two misplaced nodes and swap their values back.

Deriving the optimal solution

The key observation is that a valid BST has an increasing inorder sequence. If two values are swapped, the inorder sequence has one or two places where the order goes backward.

For example, if the correct inorder sequence is:

1, 2, 3, 4

and non-adjacent values 2 and 4 are swapped, the traversal becomes:

1, 4, 3, 2

There are two inversions: 4 > 3 and 3 > 2. The first wrong node is the larger value from the first inversion, 4. The second wrong node is the smaller value from the last inversion, 2.

If adjacent values are swapped, such as:

1, 3, 2, 4

there is only one inversion: 3 > 2. The same rule still works. The first wrong node is 3, and the second wrong node is 2.

So the whole algorithm is:

  1. Walk the tree in inorder order.
  2. Keep the previously visited node.
  3. Whenever previous.val > current.val, record an inversion.
  4. On the first inversion, save previous as the first misplaced node.
  5. On every inversion, save current as the second misplaced node.
  6. Swap the two recorded values.

This visits each node once, so the time complexity is O(n). A normal recursive or stack-based inorder traversal uses O(h) extra space, where h is the tree height. The implementation below uses Morris inorder traversal, which temporarily threads the tree so it can do the same traversal in O(1) extra space while restoring every temporary pointer before moving on.

Python solution

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:
        """Recover a BST where exactly two node values were swapped in place."""
        first_swapped: Optional["TreeNode"] = None
        second_swapped: Optional["TreeNode"] = None
        previous_node: Optional["TreeNode"] = None

        def visit_in_inorder(current_node: "TreeNode") -> None:
            nonlocal first_swapped, second_swapped, previous_node

            # In a valid BST inorder sequence, each value must be >= the
            # previous one. A drop identifies one or both swapped nodes.
            if previous_node is not None and previous_node.val > current_node.val:
                if first_swapped is None:
                    first_swapped = previous_node
                second_swapped = current_node

            previous_node = current_node

        current_node = root

        while current_node is not None:
            if current_node.left is None:
                visit_in_inorder(current_node)
                current_node = current_node.right
                continue

            # Find the inorder predecessor: the rightmost node in the left
            # subtree. Morris traversal uses its empty right pointer as a
            # temporary return path back to current_node.
            predecessor = current_node.left
            while (
                predecessor.right is not None
                and predecessor.right is not current_node
            ):
                predecessor = predecessor.right

            if predecessor.right is None:
                predecessor.right = current_node
                current_node = current_node.left
            else:
                predecessor.right = None
                visit_in_inorder(current_node)
                current_node = current_node.right

        if first_swapped is not None and second_swapped is not None:
            first_swapped.val, second_swapped.val = (
                second_swapped.val,
                first_swapped.val,
            )

The helper has one job: process nodes in inorder order and detect drops in what should be a sorted sequence. Morris traversal supplies that inorder order without a recursion stack. The temporary right pointers are restored immediately when each threaded edge is used for the second time, so the tree structure ends exactly as it started except for the corrected values.

Why this works

Only two values are wrong. In the inorder sequence, every unaffected pair remains sorted. The swapped values are therefore the only reason the sorted order can fail.

The first time the traversal sees a drop, the previous node must be too large for its position. That node is one of the swapped values. The current node is too small, but it might not be the final answer yet because the swapped values could be non-adjacent. Updating second_swapped on every drop handles both cases:

  • If the swapped values are adjacent, there is one drop and the pair from that drop is swapped back.
  • If the swapped values are non-adjacent, there are two drops. The algorithm keeps the larger node from the first drop and the smaller node from the second drop.

The traversal order is the proof. A BST is valid exactly when inorder values are sorted, so repairing the two values that break that order restores the BST invariant everywhere.

Interview follow-ups

What if the interviewer asks for the simpler stack-based solution?

Use the exact same inversion detector, but replace Morris traversal with a normal iterative inorder traversal using a stack. Push left children until reaching None, pop the next node, visit it, then move to its right child.

This works for the same reason: the algorithm only needs nodes in inorder order. The traversal mechanism does not change the misplaced-node logic. The stack version is usually easier to write under interview pressure and is often the best first answer.

The time complexity remains O(n). The extra space becomes O(h) for the stack, where h is the tree height. For a balanced tree that is O(log n), while a completely skewed tree can use O(n) space.

Why does Morris traversal still count as not changing the tree structure?

Morris traversal temporarily creates a pointer from a node’s inorder predecessor back to the current node. That pointer acts like the return address a recursion stack would normally provide.

The important detail is that each temporary pointer is removed before the traversal leaves that relationship permanently. When the algorithm sees predecessor.right is current_node, it knows it is visiting the current node after finishing its left subtree, so it restores predecessor.right to None.

Because every temporary link is undone, the final tree has the same left and right child structure as the input tree. The only permanent mutation is the intended swap of the two incorrect values. The tradeoff is code complexity: Morris traversal saves stack space, but it is easier to get wrong than recursive or iterative inorder traversal.

What if more than two nodes were misplaced?

The two-inversion trick depends on exactly two values being swapped. If more values are wrong, recording only the first large node and the last small node is no longer enough to identify all repairs.

A practical approach is to collect the full inorder list of nodes, sort the values, and then write the sorted values back into the nodes in inorder order. That restores the BST while preserving the shape. It costs O(n log n) time for sorting and O(n) space for the node list or value list.

If the interviewer wants to minimize extra memory, another option is to stream the inorder values into an external sort or use repeated selection-style passes, but those approaches are rarely worth the complexity in an interview unless memory is the central constraint.

What if duplicate values are allowed in the BST?

The answer depends on the BST convention. Some systems put duplicates on the right, some put them on the left, and some disallow them completely. The inversion check must match that convention.

If duplicates are allowed and the inorder sequence is supposed to be non-decreasing, then the detector should flag only previous.val > current.val, as the code does. Equal adjacent values are valid. If the tree requires strictly increasing values, then previous.val >= current.val would signal a violation, but that makes it harder to identify a unique repair when duplicate values exist.

The core approach still applies once the ordering rule is defined: traverse in the order that should be sorted, detect the positions that violate that order, and repair the values that caused the violations.

What if the tree nodes must not be mutated during traversal?

Then avoid Morris traversal and use a stack-based or recursive inorder traversal. Those approaches do not create temporary threads, so they are safer in codebases where concurrent readers, immutable tree contracts, or auditing rules forbid even temporary pointer changes.

The solution still mutates the two swapped values at the end because the problem requires recovery in place. The difference is that traversal itself becomes read-only. The tradeoff is extra space: the recursion stack or explicit stack uses O(h) memory instead of Morris traversal’s O(1).

Takeaway

The clean mental model is to stop thinking about the tree shape and look at the inorder sequence. A valid BST’s inorder values are sorted; swapping two nodes creates one or two drops in that sequence. Detect those drops, remember the two guilty nodes, and swap their values back.