Loading problem...
You are given the root of a binary search tree (BST) that has been corrupted. Due to a system error, the values of exactly two nodes in the tree were accidentally swapped with each other, violating the BST property.
Your task is to identify and correct the two misplaced nodes by swapping their values back, thereby restoring the tree to a valid binary search tree. You must accomplish this without altering the structure of the tree itself — only the node values should be exchanged.
A valid binary search tree is one where, for every node:
The tree is represented in level-order traversal format, where null represents an absent child node.
root = [1,3,null,null,2][3,1,null,null,2]The tree initially has node value 1 as the root with 3 as its left child. In a valid BST, the left child must be smaller than the root. Since 3 > 1, this violates the BST property. The two swapped nodes are 1 and 3. After exchanging their values, we get a valid BST with root 3 and left child 1.
root = [3,1,4,null,null,2][2,1,4,null,null,3]The tree has root 3, left child 1, and right child 4. The right subtree of node 4 contains value 2, which violates the BST property since 2 < 3 (it should not be in the right subtree of 3). The two swapped nodes are 3 and 2. After correction, the root becomes 2 and the right subtree leaf becomes 3, restoring the BST property.
root = [2,1,4,null,3,null,5][3,1,4,null,2,null,5]Initially, node 3 is incorrectly placed as the right child of node 1, and node 2 is the root. The swapped nodes are 2 (root) and 3 (right child of 1). After swapping their values, the tree becomes a valid BST with 3 as the root and 2 as the right child of 1.
Constraints