Recover a Binary Search Tree

The values of exactly two nodes of a binary search tree were swapped by mistake. Recover the tree by swapping them back, without changing its structure.

LeetCode: 99. Recover Binary Search Tree

Example

Text

    Swapped                Recovered
       6                       6
     /   \                   /   \
    8     3        ->       3     8
   / \   / \               / \   / \
  1   4 7   9             1   4 7   9

In-order: 1 8 4 6 7 3 9   ->   1 3 4 6 7 8 9

The in-order traversal of a correct BST is sorted. Swapping two values breaks that sorted sequence, and that's what both solutions use.

A tree node here is an object with left and right references. An empty subtree is null, and node fields are mutable, so no wrapper type is needed.

Brute force: sort the in-order values

Read the values in order, sort them, and write them back in order. Every node gets the value that belongs at its position. Iterator<Integer> is the standard interface for reading a sequence one value at a time with next().

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static void readInorder(TreeNode root, List<Integer> out) {
        if (root == null) return;
        readInorder(root.left, out);
        out.add(root.val);
        readInorder(root.right, out);
    }

    static void writeInorder(TreeNode root, Iterator<Integer> values) {
        if (root == null) return;
        writeInorder(root.left, values);
        root.val = values.next();
        writeInorder(root.right, values);
    }

    static void recover(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        readInorder(root, values);
        Collections.sort(values);
        writeInorder(root, values.iterator());
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6, new TreeNode(8, leaf(1), leaf(4)), new TreeNode(3, leaf(7), leaf(9)));
        recover(root);
        List<Integer> values = new ArrayList<>();
        readInorder(root, values);
        System.out.println(values + " root " + root.val);
    }
}

Output

[1, 3, 4, 6, 7, 8, 9] root 6

Time: O(n log n). Space: O(n).

Optimal: find the two misplaced values

Look for drops in the in-order sequence, places where a value is smaller than the one before it:

If the swapped values are far apart, there are two drops: 8 > 4 and 7 > 3. The first misplaced value is the larger value of the first drop (8), and the second is the smaller value of the last drop (3).
If the swapped values are neighbours in sorted order, there is only one drop, and it contains both values.

Recording "first drop's larger value" and "last drop's smaller value" covers both cases. A second pass then swaps the two values wherever they occur. The search state lives in an object with three Integer fields. null means "not seen yet".

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static class Search {
        Integer prev, first, second;
    }

    static void findDrops(TreeNode root, Search s) {
        if (root == null) return;
        findDrops(root.left, s);
        if (s.prev != null && s.prev > root.val) {
            if (s.first == null) s.first = s.prev; // only the first drop sets `first`
            s.second = root.val;                   // every drop overwrites `second`
        }
        s.prev = root.val;
        findDrops(root.right, s);
    }

    static void swapValues(TreeNode root, int a, int b) {
        if (root == null) return;
        if (root.val == a) {
            root.val = b;
        } else if (root.val == b) {
            root.val = a;
        }
        swapValues(root.left, a, b);
        swapValues(root.right, a, b);
    }

    static void recover(TreeNode root) {
        Search s = new Search();
        findDrops(root, s);
        if (s.first != null && s.second != null) {
            swapValues(root, s.first, s.second);
        }
    }

    static void inorder(TreeNode root, List<Integer> out) {
        if (root == null) return;
        inorder(root.left, out);
        out.add(root.val);
        inorder(root.right, out);
    }

    public static void main(String[] args) {
        // 3 and 8 swapped: two drops
        TreeNode root = new TreeNode(6, new TreeNode(8, leaf(1), leaf(4)), new TreeNode(3, leaf(7), leaf(9)));
        recover(root);
        List<Integer> values = new ArrayList<>();
        inorder(root, values);
        System.out.println(values);

        // 6 and 7 swapped (neighbours): one drop
        root = new TreeNode(7, new TreeNode(3, leaf(1), leaf(4)), new TreeNode(8, leaf(6), leaf(9)));
        recover(root);
        values = new ArrayList<>();
        inorder(root, values);
        System.out.println(values);
    }
}

Output

[1, 3, 4, 6, 7, 8, 9]
[1, 3, 4, 6, 7, 8, 9]

Time: O(n): two traversals. Space: O(h) for the recursion.

In Java, the search can instead keep references to the two misplaced nodes and swap their val fields directly, with no second pass. This version records the two values and swaps them in a second pass. Both have the same complexity. The value-based version relies on the values being unique, which a BST with a single swap guarantees. s.prev > root.val unboxes the Integer values to compare them numerically, which is safe because prev is checked for null first.

The O(1)-space Morris traversal temporarily rewires right links into cycles and restores them afterwards. It works with mutable references, but it is longer to write correctly, and O(h) recursion is enough for this lesson.

Edge cases

Swapped values adjacent in sorted order: a single drop; first and second both come from it.
Root involved in the swap: handled like any other node.
Tree already correct: no drops, and nothing changes.