A large-scale system maintains critical ordered datasets using a Binary Search Tree (BST), where:
- left subtree contains smaller values
- right subtree contains larger values
Due to a system bug, exactly two nodes in the BST have been swapped, violating the BST property.
This issue can lead to:
- incorrect query results
- invalid ranking systems
- broken ordering guarantees
The system needs a recovery mechanism that:
- identifies the two misplaced nodes
- restores the BST without changing the tree structure
⚠️ Constraint:
You must fix the tree in-place, without rebuilding it.
This is a classic advanced interview problem frequently asked in Google, Amazon, Meta, Microsoft, and other top companies.
Your Task
Given the root of a BST where exactly two nodes are swapped by mistake:
👉 Recover the tree by swapping the values of the two nodes back.
Do not change the tree structure, only modify node values.
Input Format
Each node:
TreeNode { int val; TreeNode left; TreeNode right;}
Output Format
- Return the root of the corrected BST