Restore a Search Tree After Two Values Were Swapped

Medium30–35 min

Topics

Binary Search TreeBSTInorderRepair

Companies

AmazonMicrosoftGoogleFacebookBloomberg

You are given the root of a binary tree that was a valid binary search tree with distinct values, until the values of exactly two of its nodes were swapped with each other. Restore the tree by putting the two values back where they belong, without changing the shape of the tree, and return its root.

The inorder sequence of a search tree is sorted, so a swap leaves the sequence sorted except for two exchanged values. Comparing with a sorted copy finds them; a single inorder walk that watches for a value smaller than its predecessor finds them without any extra storage.

Test Case 1:

Input:root = [50, 30, 20, 70, 40, 60, 80]

Output:[50, 30, 70, 20, 40, 60, 80]

Explanation:20 and 70 were swapped. Listing the tree in order gives 70, 30, 40, 50, 60, 20, 80, which is out of order at two places; swapping 70 and 20 back restores the sorted order.

Test Case 2:

Input:root = [10, 20, 30]

Output:[20, 10, 30]

Explanation:The root 20 and its left child 10 were swapped (they are neighbours in sorted order), which creates only ONE out-of-order pair in the inorder list (20, 10, 30).

Test Case 3:

Input:root = [40, 20, 60, 10, 50, 30, 70]

Output:[40, 20, 60, 10, 30, 50, 70]

Explanation:30 and 50 were exchanged: 50 sits in the left subtree of 40 (it must be smaller than 40) and 30 in the right subtree (it must be larger). Swapping them back fixes both sides at once.

Constraints

◆2 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000
◆The tree WAS a binary search tree, but the values of exactly two of its nodes have been swapped with each other; the shape is unchanged. It is given by its root node
◆Restore the search-tree property by putting the two values back where they belong — change only the values of those two nodes, not the shape
◆Return the root of the repaired tree (checked as a level-order list)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Compare the Inorder Values With Their Sorted Copy

Brute

The inorder sequence of a search tree is sorted, so the damaged tree's inorder sequence is a sorted list with exactly two values exchanged. Collect the nodes in inorder, sort a copy of their values, and compare the two lists position by position: exactly two positions differ. The nodes at those two positions are the swapped ones; exchange their values. The sort costs O(n log n) and both lists take O(n) space.

TimeO(n log n)

SpaceO(n)

Java

Try it out

class Solution {
    public TreeNode fixSwappedNodes(TreeNode root) {
        List<TreeNode> nodes = new ArrayList<>();
        collect(root, nodes);
        List<Integer> sorted = new ArrayList<>();
        for (TreeNode n : nodes) sorted.add(n.val);
        Collections.sort(sorted);
        TreeNode first = null, second = null;
        for (int i = 0; i < nodes.size(); i++) {
            if (nodes.get(i).val != sorted.get(i)) {
                if (first == null) first = nodes.get(i);
                else second = nodes.get(i);
            }
        }
        if (first != null && second != null) {
            int tmp = first.val;
            first.val = second.val;
            second.val = tmp;
        }
        return root;
    }

    private void collect(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        collect(node.left, nodes);
        nodes.add(node);
        collect(node.right, nodes);
    }
}

Optimal — One Inorder Walk That Spots the Out-of-Order Pairs

Optimal

Walk the tree in inorder while remembering the previously visited node (prev). Whenever prev.val > node.val, the sequence goes DOWN — an inversion. Swapping two values creates either two inversions (non-neighbours in sorted order) or one (neighbours). At the first inversion, the bigger value prev is the first culprit; keep updating the second culprit to the current node at every inversion, so after the walk second is the smaller value that was pushed too far right (from the first inversion if there is only one). Swap the values of first and second. One pass and O(h) recursion space; no sorting and no list.

TimeO(n)

SpaceO(h)