Repair BST

Tags

Repair BST

Category

Binary Search Trees

Difficulty

Hard

Problem Statement

Given a Binary Search Tree where exactly two nodes have been swapped by mistake (their values were exchanged), repair the BST by swapping them back. The repair should be done in place, restoring the BST property that for every node, all values in the left subtree are less and all values in the right subtree are greater.

Intuition

An in-order traversal of a valid BST produces a strictly sorted sequence. When two nodes are swapped, the in-order sequence will have exactly one or two "inversions" (places where a value is greater than the next value). If the swapped nodes are adjacent in the in-order sequence, there is one inversion. If they are not adjacent, there are two inversions. By identifying these inversion points, we can find the two swapped nodes and swap their values back.

Approach

  1. Perform an in-order traversal of the BST while tracking the previously visited node.
  2. When previous.value > current.value, an inversion is found.
  3. At the first inversion: record previous as the first problematic node and current as the second (tentatively, in case the swapped nodes are adjacent).
  4. At the second inversion (if it exists): update the second problematic node to current.
  5. After the traversal, swap the values of the two identified nodes.
  6. This can be done iteratively using a stack or recursively.

Pseudocode

function repairBst(root):
    nodeOne = null
    nodeTwo = null
    previousNode = null

    inOrderTraverse(root, previousNode, nodeOne, nodeTwo)

    // Swap values to repair
    temp = nodeOne.value
    nodeOne.value = nodeTwo.value
    nodeTwo.value = temp

    return root

function inOrderTraverse(node, previousNode, nodeOne, nodeTwo):
    if node is null:
        return

    inOrderTraverse(node.left, previousNode, nodeOne, nodeTwo)

    if previousNode is not null and previousNode.value > node.value:
        if nodeOne is null:
            nodeOne = previousNode
        nodeTwo = node

    previousNode = node

    inOrderTraverse(node.right, previousNode, nodeOne, nodeTwo)

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. The in-order traversal visits every node exactly once.
  • Space: O(h) where h is the height of the tree, for the recursion stack. Can be reduced to O(1) using Morris traversal.

Key Insights

  • In-order traversal of a BST yields sorted output — this is the fundamental property exploited here.
  • With two swapped nodes, there are at most two inversions in the in-order sequence.
  • The first misplaced node is always the previous node at the first inversion. The second misplaced node is the current node at the last inversion.
  • We only swap values, not nodes themselves, which avoids complex pointer manipulation.
  • Morris traversal can achieve O(1) space by temporarily modifying the tree structure (threading), but adds complexity.

Edge Cases

  • The two swapped nodes are adjacent in the in-order sequence — only one inversion is found, and we swap previous and current from that single inversion.
  • The two swapped nodes are the leftmost and rightmost nodes — they produce two inversions at the extremes of the traversal.
  • One of the swapped nodes is the root — the algorithm handles this naturally since it operates on values.
  • The tree has only two nodes — they must be the swapped pair.
  • The swapped nodes are parent and child — still handled correctly by the in-order approach.

Linked mentions