Practice/Microsoft/Leetcode 99. Recover Binary Search Tree

Leetcode 99. Recover Binary Search Tree

CodingOptional

Problem

You are given the root of a binary search tree (BST) where exactly two nodes have been mistakenly swapped by accident. Your task is to fix the tree without altering its structure—only by swapping the values of the two incorrect nodes back to their proper positions.

A valid BST must satisfy the property that for every node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are greater than the node's value.

You must modify the tree in-place and should not return anything.

Requirements

1. Identify the two nodes whose values were swapped
2. Restore the BST property by swapping their values back
3. Do not change the tree structure (only swap values)
4. Modify the tree in-place without creating a new tree
5. Handle both adjacent and non-adjacent swapped nodes

Constraints

• The number of nodes in the tree is in the range [2, 1000]
• -2³¹ <= Node.val <= 2³¹ - 1
• Exactly two nodes have been swapped
• Follow up: Can you solve it using O(1) space complexity (excluding recursion stack)?

Examples

Example 1:

` Input: root = [1,3,null,null,2] Tree structure: 1
3 / 2

Output: [3,1,null,null,2] Corrected tree: 3
1
2

Explanation: Nodes with values 1 and 3 were swapped. After fixing, the inorder traversal [1,2,3] becomes valid. `

Example 2:

` Input: root = [3,1,4,null,null,2] Tree structure: 3 /
1 4 / 2

Output: [2,1,4,null,null,3] Corrected tree: 2 /
1 4 / 3

Explanation: Nodes with values 2 and 3 were swapped. `