Recover Binary Search Tree — Solution

Problem

Two nodes in a binary search tree have been silently swapped, breaking the BST property. Your task is to fix the tree by returning those two nodes to their correct positions — without changing the tree's structure, just their values.

Example — two non-adjacent nodes swapped:

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

• Input: the tree above (nodes 3 and 2 were swapped)
• Output: swap the values back so the tree becomes a valid BST

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

• Explanation: in-order reads 1 → 3 → 2 → 4 (out of order); swapping 3 and 2 restores 1 → 2 → 3 → 4

Counter-example — adjacent nodes swapped:

[2,3,4]

Nodes 2 and 3 are neighbors in in-order. In this case there is only one violation (3 > 2 is not sorted), but the fix is the same: swap the two nodes' values.

Intuition

A valid BST's in-order traversal produces a perfectly sorted sequence. If exactly two nodes are swapped, that sorted sequence has either one or two spots where a number is larger than the one that follows it. The first such "bump" always points to the first misplaced node; the last one always points to the second. Find both, then swap their values.

Approach 1 — Collect In-Order, Scan for Violations

Collect all nodes in in-order into a list, then scan consecutive pairs to locate the two swapped nodes.

1. Run a recursive in-order traversal and append each node (not just its value) into nodes_inorder.
2. Walk through the list comparing nodes_inorder[i].val with nodes_inorder[i+1].val.
3. Whenever nodes_inorder[i].val > nodes_inorder[i+1].val, record the second node in second_wrong (keep overwriting — the last violation wins).
4. Record the first node in first_wrong only on the very first violation, because the first misplaced node never changes across violations.
5. Swap the values of first_wrong and second_wrong.

1def recoverTree(self, root: Optional[TreeNode]) -> None:
2    nodes_inorder = []
3
4    def collect_inorder(node):
5        if not node:
6            return
7        collect_inorder(node.left)
8        nodes_inorder.append(node)
9        collect_inorder(node.right)
10
11    collect_inorder(root)
12
13    first_wrong = second_wrong = None
14    for i in range(len(nodes_inorder) - 1):
15        if nodes_inorder[i].val > nodes_inorder[i + 1].val:
16            second_wrong = nodes_inorder[i + 1]  # always update so we land on the right end node
17            if first_wrong is None:              # only capture first_wrong once — it never changes
18                first_wrong = nodes_inorder[i]
19
20    first_wrong.val, second_wrong.val = second_wrong.val, first_wrong.val

Time: O(n) — visits every node once during traversal and once during the scan.
Space: O(n) — the list stores a reference to every node.

Approach 2 — Inline Violation Tracking (O(h) Space)

Instead of storing the whole list, track a prev_node pointer during in-order traversal and detect violations on the fly.

1. Traverse the tree in-order, keeping a prev_node reference to the last visited node.
2. At each step, if prev_node.val > current_node.val, a violation exists: set first_wrong = prev_node (only on the first violation) and second_wrong = current_node (always overwrite).
3. After traversal completes, swap first_wrong.val and second_wrong.val.

1def recoverTree(self, root: Optional[TreeNode]) -> None:
2    self.prev_node = None
3    self.first_wrong = None
4    self.second_wrong = None
5
6    def find_violations(node):
7        if not node:
8            return
9        find_violations(node.left)
10
11        if self.prev_node and self.prev_node.val > node.val:
12            if self.first_wrong is None:
13                self.first_wrong = self.prev_node  # prev is the out-of-place "high" node
14            self.second_wrong = node               # current is the out-of-place "low" node; keep updating
15
16        self.prev_node = node
17        find_violations(node.right)
18
19    find_violations(root)
20    self.first_wrong.val, self.second_wrong.val = self.second_wrong.val, self.first_wrong.val

Time: O(n) — single in-order pass.
Space: O(h) — only the call stack, where h is the tree height (O(log n) for balanced, O(n) worst case for a skewed tree).

Complexity Summary

Common Mistakes

• Updating first_wrong on the second violation — in the two-violation case, first_wrong is set exactly once (at the first violation) and never touched again; overwriting it gives the wrong node to swap.
• Stopping after the first violation — when swapped nodes are non-adjacent in in-order, a second violation occurs later and second_wrong must be updated to that later node, not the one from the first violation.
• Swapping node pointers instead of values — the problem says don't change the structure; just swap .val on the two misfiled nodes.
• Python scoping trap with prev — assigning to a plain outer-scope variable inside a nested function silently creates a local one. Using self.prev_node (instance variable) sidesteps this completely.
• Off-by-one in the scan loop — when scanning the collected list, the loop must stop at len - 1 so nodes[i + 1] is always in bounds; indexing to len causes an index error on the last element.

Related Problems

• Binary Tree Inorder Traversal — the exact traversal pattern this problem is built on
• Kth Smallest Element in a BST — same in-order traversal with a running counter instead of a violation detector
• Delete Node in a BST — another problem that requires understanding the BST structural contract
• Lowest Common Ancestor of a Binary Search Tree — exploits BST ordering the same way this problem does
• Convert Sorted Array to Binary Search Tree — builds intuition for the link between sorted order and BST structure