Repair Two Swapped BST Values

SilverShow difficulty

10000ms500MBSep 30, 2026

You are given a binary tree root that was a binary search tree until exactly two nodes had their values swapped. Swap them back and return the root of the repaired tree.

The tree's shape does not change.

You can assume all values are distinct, exactly two values were swapped, and the repaired tree is a valid binary search tree.

Tree Encoding

Your function receives root as a TreeNode and returns the root of the repaired tree the same way. The node type is provided for you, with val, left, and right fields.

The examples below write trees as their level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how trees are displayed; the encoding and decoding are done for you.

Constraints

The number of nodes in root is in the range $[2, 10^4]$ .
$-10^9 \leq$ Node.val $\leq 10^9$
All Node.val are unique.
Exactly two values have been swapped from a valid binary search tree.

Examples

Example 1

Input

root = [1, 3, null, null, 2]

root

Output

[3, 1, null, null, 2]

Explanation

3 sits in the left subtree of 1 but is larger than it. Swapping the values 1 and 3 gives [3,1,null,null,2], a valid binary search tree.

Example 2

Input

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

root

Output

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

Explanation

2 sits in the right subtree of 3 but is smaller than it. Swapping the values 2 and 3 gives [2,1,4,null,null,3], a valid binary search tree.

Example 3

Input

root = [1, 2]

root

Output

[2, 1]

Explanation

2 is the left child of 1 but is larger than it. Swapping the two values gives [2,1].

Loading editor...

Samples 3

Custom 0

sample

Include in Run

root =tree

Expected

[3, 1, null, null, 2]

Tree Encoding

Your function receives root as a TreeNode and returns the root of the repaired tree the same way. The node type is provided for you, with val, left, and right fields.