DSA Recovering a Swapped BST

The problem

A binary search tree holds distinct values in sorted inorder order. Exactly two values have been swapped inside their nodes. No node has moved.

The repair swaps those two values back. The tree shape stays untouched. The answer is complete when the inorder walk reads sorted again.

cases = [
    ([1, 3, 2, 4], (3, 2)),
    ([1, 2, 6, 4, 5, 3, 7], (6, 3)),
    ([7, 2, 3, 4, 5, 6, 1], (7, 1)),
]
for order, pair in cases:
    print("inorder:", order, "swapped pair:", pair)

Read one row at a time. The first row swaps neighbours in the walk. The other rows swap values far apart in the walk. That difference decides how many drops the walk shows.

Intuition: a sorted walk, and where it drops

An inorder walk visits the left subtree, then the node, then the right subtree. A healthy search tree therefore walks in sorted order. Damage must appear as a place where the walk drops.

A drop is a neighbouring pair where the earlier value is larger. The first guess swaps the two values at the first drop. That guess fails when the swapped values sit far apart, because a far-apart swap creates two drops.

order = [1, 2, 6, 4, 5, 3, 7]
drops = [i for i in range(1, len(order)) if order[i] < order[i - 1]]
print("drop positions:", drops)
fixed = order[:]
i = drops[0]
fixed[i - 1], fixed[i] = fixed[i], fixed[i - 1]
print("after swapping the first drop pair:", fixed)
print("sorted:", fixed == sorted(fixed))

Swapping 6 and 4 repairs the first drop. The second drop, from 5 to 3, survives. One drop gets a local fix, and the real damage is not local.

Brute force: try every pair swap

The brute force swaps each pair of positions in the walk in turn. It keeps the first swap that makes the walk sorted. A counter records how many pairs it tested.

def brute(order):
    target = sorted(order)
    tried = 0
    for i in range(len(order)):
        for j in range(i + 1, len(order)):
            tried += 1
            trial = order[:]
            trial[i], trial[j] = trial[j], trial[i]
            if trial == target:
                return (order[i], order[j]), tried
    return None, tried

pair, tried = brute([1, 2, 6, 4, 5, 3, 7])
print("swapped pair:", pair)
print("pair swaps tried:", tried)
pair, tried = brute([7, 2, 3, 4, 5, 6, 1])
print("swapped pair:", pair)
print("pair swaps tried:", tried)

The brute force always finds the pair. Its bill is the pair count, and each trial also pays a full sorted check. The next section keeps the drops and drops the trials.

The optimal solution: read the drops, swap the outer values

The rule is one sentence. With two drops, the swapped values are the larger value of the first drop and the smaller value of the second drop, and with one drop they are that drop's two values.

One walk collects both candidates. This article's version stores the walk in a list for clarity. The same rule needs only the previous node, so a leaner walk can skip the list. Swapping the two node values at the end repairs the tree in place.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def inorder_nodes(node, found):
    if node is None:
        return
    inorder_nodes(node.left, found)
    found.append(node)
    inorder_nodes(node.right, found)

def recover(root):
    nodes = []
    inorder_nodes(root, nodes)
    first = None
    second = None
    for i in range(1, len(nodes)):
        if nodes[i].value < nodes[i - 1].value:
            if first is None:
                first = nodes[i - 1]
            second = nodes[i]
    first.value, second.value = second.value, first.value
    return first.value, second.value

trees = [
    TreeNode(3, TreeNode(1), TreeNode(4, TreeNode(2))),
    TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(6)),
             TreeNode(3, TreeNode(5), TreeNode(7))),
    TreeNode(4, TreeNode(2, TreeNode(7), TreeNode(3)),
             TreeNode(6, TreeNode(5), TreeNode(1))),
]
for tree in trees:
    before_nodes = []
    inorder_nodes(tree, before_nodes)
    before_vals = [n.value for n in before_nodes]
    pair = recover(tree)
    after = []
    inorder_nodes(tree, after)
    print("before:", before_vals,
          "swapped back:", tuple(sorted(pair)),
          "after:", [n.value for n in after])

All three walks read sorted after one swap each. The middle tree swaps 6 and 3, the outer values of its two drops. The first tree has one drop, so its own two values swap.

Walkthrough: the walk over [1, 2, 6, 4, 5, 3, 7]

The walk visits one value at a time. The state is the previous value, the first candidate, and the second candidate. Each drop updates the state in a printed step.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(6)),
                TreeNode(3, TreeNode(5), TreeNode(7)))
nodes = []
def collect(node):
    if node is None:
        return
    collect(node.left)
    nodes.append(node)
    collect(node.right)
collect(tree)
prev = None
first = None
second = None
for node in nodes:
    note = ""
    if prev is not None and node.value < prev.value:
        if first is None:
            first = prev
            note = "drop: first candidate set"
        else:
            note = "drop: second candidate updated"
        second = node
    print("visit", node.value, "| prev:", None if prev is None else prev.value,
          "| first:", None if first is None else first.value,
          "| second:", None if second is None else second.value, note)
    prev = node
print("swap back:", first.value, "and", second.value)

The first drop, 6 down to 4, sets the first candidate to 6. The second drop, 5 down to 3, sets the second candidate to 3. No other step touches the state.

Complexity

The optimal walk visits each of the n nodes once, so its time is O(n). The lean version stores only the previous node and two candidates besides the walk stack, so its extra space is O(1) beyond the stack.

The brute force tries up to n times n minus 1, divided by 2, pairs. Each trial pays a sorted check over n values, so its time grows like O(n^3).

for n in [7, 15, 31]:
    pairs = n * (n - 1) // 2
    print("nodes", n, "- brute pair trials:", pairs,
          " brute check steps up to:", pairs * n,
          " optimal visits:", n)

Counts beat clocks here. At 31 nodes the brute force faces 465 trials, each with a full check. The drop rule still pays one visit per node.

Edge cases and pitfalls

Neighbouring swapped values make exactly one drop. Treating that drop as the first of two is the classic mistake, and it waits forever for a second drop that never comes. The rule handles it because the first drop sets both candidates, and a later drop moves only the second one.

Swapping nodes instead of values is the other mistake. It changes the tree shape and can break other links. The repair exchanges only the two stored values.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def inorder_values(node, found):
    if node is None:
        return
    inorder_values(node.left, found)
    found.append(node.value)
    inorder_values(node.right, found)

def recover(root):
    nodes = []
    def collect(node):
        if node is None:
            return
        collect(node.left)
        nodes.append(node)
        collect(node.right)
    collect(root)
    first = None
    second = None
    for i in range(1, len(nodes)):
        if nodes[i].value < nodes[i - 1].value:
            if first is None:
                first = nodes[i - 1]
            second = nodes[i]
    if first is None:
        return None
    first.value, second.value = second.value, first.value
    return (second.value, first.value)

def shape(node):
    if node is None:
        return None
    return (shape(node.left), shape(node.right))

two = TreeNode(1, TreeNode(2))
before_shape = shape(two)
print("two-node swap:", recover(two))
vals = []
inorder_values(two, vals)
print("two-node inorder after:", vals, "shape kept:", shape(two) == before_shape)
single = TreeNode(9)
print("single node, no swap found:", recover(single), "value:", single.value)

The two-node tree repairs with one drop and keeps its shape. A single node has no pair and no drop, so the search reports nothing. Real inputs promise exactly one swapped pair, so that report means the promise was broken.