Medium · Trees

Recover Binary Search Tree

Given the root of a binary search tree with distinct values in which the values of exactly two nodes were swapped by mistake, restore the tree in place so that it is a valid binary search tree again, without changing its structure.

Examples

Example 1

[3,1,2] (2 & 3 swapped)

Output: sorted: 1 2 3

Example 2

[2,1,4,null,3] (2 & 3 swapped)

Output: sorted: 1 2 3 4

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.

More Trees problems