root of a binary search tree: for every node, all values in its left subtree are smaller than its value and all values in its right subtree are larger. All values are distinct.
By mistake, the values of exactly two nodes were swapped, which broke the search tree property. Fix the tree: put those two values back where they belong without changing the tree's shape.
Return the root of the fixed tree; fixing it in place is fine.
An O(n)-memory solution is the obvious one. Can you manage with O(1) extra memory?root=tree_node([5, 8, 3, 1, 4]) → [5, 3, 8, 1, 4]
The in-order walk gives 1, 8, 4, 5, 3: the 8 and the 3 are out of place. Swapping their values yields [5, 3, 8, 1, 4], where every node has smaller values on its left and larger ones on its right.
root=tree_node([3, 1, 2]) → [2, 1, 3]
The neighbouring values 2 and 3 were mixed up: after the swap the root holds 2 and its right child holds 3.
root=tree_node([10, 12, 15, 2, 7, 4, 20]) → [10, 4, 15, 2, 7, 12, 20]
root=tree_node([5, 8, 3, 1, 4])
[5, 3, 8, 1, 4]
Run checks the first 3 tests in your browser. Submit checks all 35 tests on the server, hidden ones included.