Full lesson preview

Recover a swapped BST

Two nodes in a binary search tree (BST) were swapped by mistake. Recover the BST by fixing the node values without changing the tree structure.

Python practice25 minTrees & Binary TreesAdvancedLast updated March 29, 2026

Problem statement

You are given the root of a binary search tree (BST) in which exactly two nodes' values were swapped by mistake. Your task is to recover the tree by swapping the values of the two incorrect nodes back so that the tree becomes a valid BST. You must not change the tree structure (i.e., do not add/remove nodes or change links). Aim for O(n) time and O(h) extra space (where h is the height of the tree). Return the root after recovery (returning the root helps with testing); the function should also modify the input tree in-place.

Task

Identify the two swapped nodes in a BST and restore the tree so that an inorder traversal yields a sorted sequence. Implement an O(n) time, O(h) extra space solution.

Examples

Example 1 - simple adjacent swap

Input

[3, 1, 2]

Output

[1, 2, 3]

The tree built from level-order [3,1,2] has nodes 3 and 2 swapped relative to a valid BST [2,1,3]. After recovery the inorder traversal is [1, 2, 3].

Input format

A level-order representation list of integers and nulls (None) to build the tree: e.g. [3,1,4,None,None,2]. Use the provided build_tree helper to construct the tree.

Output format

Return the root (modified in place). For testing we will use inorder_values(recover_bst(root)) which should return a Python list of node values in ascending order.

Constraints

1 <= number of nodes <= 10^4. Node values are integers (they may be unique for this problem). Exactly two node values have been swapped.

Samples

Sample 1

Input

[3,1,4,None,None,2]

Output

[1, 2, 3, 4]

This corresponds to the common LeetCode example. After fixing the swapped nodes, the inorder traversal is sorted.