☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Correct BST with two nodes swapped

Hard TUF ID 97 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

The keys of exactly two nodes of a binary search tree were swapped by mistake. Repair the tree in place, without changing its structure: no nodes are added, removed, or moved, only keys are changed. The method returns nothing.

Constraints (LeetCode version): 2 to 1000 nodes, keys anywhere in the 32-bit signed range. The follow-up asks for O(1) extra space.

Trees are written in LeetCode level order.

Example 1

broken [1, 3, null, null, 2]        fixed [3, 1, null, null, 2]

      1                                   3
     /                                   /
    3                                   1
     \                                   \
      2                                   2

In-order of the broken tree is 3 2 1; swapping 3 and 1 makes it 1 2 3.

Example 2

broken [3, 1, 4, null, null, 2]     fixed [2, 1, 4, null, null, 3]

In-order of the broken tree is 1 3 2 4; swapping 3 and 2 makes it sorted.

The key observation

The in-order sequence of a valid BST is sorted. Swapping two keys of a sorted sequence breaks it in a very specific way. Call a position where a key is larger than the key right after it a drop.

So one in-order pass that remembers the first drop’s left element (first), the first drop’s right element (middle), and the second drop’s right element (last) identifies both keys: swap first with last if a second drop exists, else with middle.

Approach 1: Brute force, sort and write back

Intuition. A BST with a fixed shape and a fixed set of keys has exactly one valid assignment of keys to nodes: the k-th node in in-order must hold the k-th smallest key. So read all keys in in-order, sort them, and write them back in in-order. This does not even use the fact that only two keys moved.

Algorithm.

  1. Collect the keys with an in-order traversal.
  2. Sort them.
  3. Traverse in-order again and overwrite the k-th visited node with the k-th sorted key.
static void bruteForce(TreeNode root) {
    List<Integer> keys = new ArrayList<>();
    collectInorder(root, keys);
    Collections.sort(keys);
    int[] next = {0};
    writeInorder(root, keys, next);
}

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

static void writeInorder(TreeNode node, List<Integer> keys, int[] next) {
    if (node == null) return;
    writeInorder(node.left, keys, next);
    node.val = keys.get(next[0]++);              // the k-th in-order node gets the k-th smallest key
    writeInorder(node.right, keys, next);
}

Complexity. Time O(n log n) for the sort. Space O(n) for the list, plus O(h) recursion.

Approach 2: Optimal, one in-order pass

Intuition. Apply the key observation directly. Walk the tree in in-order, comparing each node with the previously visited one. A drop is prev.val > node.val. Record the nodes around the first drop, then the right node of a second drop if one appears. After the walk, swap the two keys back. Keeping the scan state in a small object lets the same logic be reused by Approach 3.

Algorithm.

  1. In-order traversal; at each node call visit.
  2. visit: if prev exists and prev.val > node.val, then on the first drop set first = prev, middle = node; on a second drop set last = node. Then set prev = node.
  3. repair: swap first.val with last.val if last was found, otherwise with middle.val.
static class Scan {
    TreeNode prev, first, middle, last;

    void visit(TreeNode node) {
        if (prev != null && prev.val > node.val) {
            if (first == null) { first = prev; middle = node; }   // first drop: prev is the too-large key
            else last = node;                                     // second drop: node is the too-small key
        }
        prev = node;
    }

    void repair() {
        if (first == null) return;                       // no drop: the tree is already valid
        TreeNode other = last != null ? last : middle;   // one drop means the swapped keys were neighbours
        int t = first.val;
        first.val = other.val;
        other.val = t;
    }
}

The traversal itself is a plain recursive in-order that hands each node to the scanner:

static void optimal(TreeNode root) {
    Scan scan = new Scan();
    inorder(root, scan);
    scan.repair();
}

static void inorder(TreeNode node, Scan scan) {
    if (node == null) return;
    inorder(node.left, scan);
    scan.visit(node);
    inorder(node.right, scan);
}

Dry run on the tree [10, 5, 15, 2, 7, 12, 20] with 5 and 20 swapped. The broken in-order is 2 20 7 10 12 15 5.

visit prev drop? first middle last
2 none no      
20 2 no      
7 20 yes, first drop 20 7  
10 7 no 20 7  
12 10 no 20 7  
15 12 no 20 7  
5 15 yes, second drop 20 7 5

last exists, so swap 20 and 5. The tree is repaired.

Complexity. Time O(n): one traversal. Space O(h) for the recursion stack: O(log n) balanced, O(n) for a chain. That stack is what the follow-up wants removed.

Approach 3: Optimal in O(1) space, Morris traversal

Intuition. Morris in-order traversal visits nodes in in-order without a stack or recursion, by temporarily borrowing null pointers. For a node cur with a left subtree, its in-order predecessor is the rightmost node of that left subtree, and that node’s right pointer is null. Point it at cur (a thread), then go left. When the walk later reaches that predecessor and follows its right pointer, it climbs straight back to cur. On that second arrival we know the left subtree is finished, so we remove the thread, visit cur, and go right. Every thread is removed before the walk ends, so the shape is unchanged.

The Scan object does not care how nodes are delivered, only that they arrive in in-order, so the drop detection and the repair are reused unchanged.

Algorithm.

  1. cur = root. While cur is not null:
  2. If cur has no left child, visit it and go right.
  3. Otherwise find pred, the rightmost node of cur.left (stopping if its right already points to cur).
  4. If pred.right is null, set the thread pred.right = cur and go left.
  5. Otherwise remove the thread, visit cur, and go right.
  6. After the loop, call repair.
static void morris(TreeNode root) {
    Scan scan = new Scan();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            scan.visit(cur);
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;                       // rightmost node of the left subtree
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur;                           // first arrival: thread back to cur, go left
                cur = cur.left;
            } else {
                pred.right = null;                          // second arrival: left side done, remove thread
                scan.visit(cur);
                cur = cur.right;
            }
        }
    }
    scan.repair();
}

Complexity. Time O(n). Finding a predecessor walks down the right spine of a left subtree, but each such spine is walked exactly twice, once to create the thread and once to remove it, and the spines of different nodes do not overlap. So every edge is traversed a constant number of times. Space O(1): a few pointers.

The repair runs only after the traversal ends. Swapping keys would not disturb the threads, but we cannot know which node to swap with until we know whether a second drop exists.

Edge cases and pitfalls