AlgoMaster Logo

Recover Binary Search Tree

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

A valid BST has one defining property: an in-order traversal produces values in strictly increasing order. If exactly two nodes have their values swapped, the in-order sequence will have either one or two "inversions," places where a value is greater than the one that follows it.

Consider a sorted sequence like [1, 2, 3, 4, 5]. If we swap 2 and 5, we get [1, 5, 3, 4, 2]. There are two inversions here: 5 > 3 and 4 > 2. The first swapped node is the larger element in the first inversion (5), and the second swapped node is the smaller element in the last inversion (2).

When the swapped nodes are adjacent in the in-order sequence, only one inversion appears. Swapping 3 and 4 gives [1, 2, 4, 3, 5], and the single inversion 4 > 3 contains both swapped nodes.

Every approach below builds on this: perform an in-order traversal, detect the inversions, identify the two misplaced nodes, and swap their values back.

Key Constraints:

  • Number of nodes in [2, 1000] → With at most 1000 nodes, an O(n log n) sort-based approach runs fine, but O(n) solutions exist and the follow-up pushes toward O(1) extra space.
  • -2^31 <= Node.val <= 2^31 - 1 → Node values span the full signed 32-bit range, including the extremes. Any sentinel like "negative infinity" must sit outside this range, so comparing actual node pointers (rather than a sentinel value) avoids the issue.
  • Exactly two nodes swapped → Exactly one swap is guaranteed, so the in-order traversal has either one or two inversions, never zero or three. The algorithms rely on this to know that recording the first "too large" node and the last "too small" node is enough.

Approach 1: In-Order Traversal with Sorting

Intuition

Collect all values via in-order traversal, sort them, then walk the tree again in-order and write the sorted values back into the nodes. A correct BST is exactly the one whose in-order sequence is sorted, so once the values come out in sorted order the two swapped values land back in their proper positions.

Algorithm

  1. Perform an in-order traversal of the BST and collect all node values into a list.
  2. Sort the list to get the correct order.
  3. Perform a second in-order traversal, assigning the sorted values back to each node.

Visualization and Code

Loading animation...

Sorting touches all n values to relocate only two of them. The next approach detects the inversions during a single in-order traversal and skips both the sort and the value list.

Approach 2: In-Order Traversal with Inversion Detection

Intuition

In a valid BST, the in-order traversal is strictly increasing. When two nodes are swapped, this creates "inversions," pairs of consecutive elements in the in-order sequence where the first is larger than the second.

There are two cases. If the swapped nodes are not adjacent in the in-order sequence, two inversions appear. The first swapped node is the larger element in the first inversion, and the second swapped node is the smaller element in the second inversion. If the swapped nodes are adjacent, only one inversion appears, and both swapped nodes are in that single inversion.

The algorithm walks the in-order traversal, tracks the previous node, and treats every prev.val > current.val as an inversion. On the first inversion, record prev as the first bad node and current as the second. On a later inversion, update only the second bad node. After the traversal, swap the values of the two recorded nodes.

Algorithm

  1. Perform an in-order traversal, keeping track of the previously visited node.
  2. Whenever prev.val > current.val (an inversion):
    • If this is the first inversion, set first = prev and second = current.
    • If this is the second inversion, update second = current.
  3. After traversal, swap the values of first and second.

Visualization and Code

Loading animation...

The time complexity is optimal, but the recursion stack uses O(h) space. The follow-up asks for O(1) space, which requires an in-order traversal that uses no stack or recursion. Morris traversal does exactly that.

Approach 3: Morris In-Order Traversal (O(1) Space)

Intuition

Morris traversal walks a binary tree in-order using O(1) extra space, with no recursion and no explicit stack. It temporarily modifies the tree itself to create "threads," pointers from a node's in-order predecessor back to the node, so the traversal can return upward without a stack to remember where it came from.

Before descending into a node's left subtree, find the rightmost node in that left subtree (the in-order predecessor). Set that node's right pointer to the current node. This temporary link routes control back to the current node once the left subtree is fully processed. On the way back, the link is removed so the tree is restored to its original shape.

Because the threads are removed as the traversal passes back through them, the tree is fully restored by the time the algorithm finishes. During the traversal, though, the structure is mutated, so this approach is unsuitable when the tree is shared across threads or must not be modified mid-traversal.

The inversion-detection logic is identical to Approach 2: track the previous node and record the offending nodes whenever prev.val > current.val.

Algorithm

  1. Initialize current = root, and set first, second, and prev to null.
  2. While current is not null:
    • If current has no left child: Visit the node (check for inversion with prev), then move right.
    • If current has a left child: Find the in-order predecessor (rightmost in left subtree).
      • If predecessor's right is null: create thread, move left.
      • If predecessor's right is current: remove thread, visit node, move right.
  3. After traversal, swap the values of first and second.

Visualization and Code

Loading animation...