Identify Swapped Nodes in a Malformed BST
At Shiprocket, efficient data management is crucial for systems like order tracking and inventory management. We often rely on Binary Search Trees (BSTs) to store unique identifiers (e.g., product SKUs or order IDs) for quick lookups and range queries. Recently, an unforeseen system glitch or a manual data entry error led to a situation where exactly two nodes in one of our critical BSTs had their values inadvertently swapped. This corruption has disrupted the BST property, causing incorrect data retrieval.
Your task is to implement a function findSwappedNodes that identifies the values of these two mistakenly swapped nodes. The function should traverse the malformed BST, pinpoint the two values that are out of place, and return them.
Specifically, you need to:
Function Signature (TypeScript):
function findSwappedNodes(root: TreeNode | null): number[]
Parameters:
root: The root of a binary tree. This tree was originally a valid Binary Search Tree, but exactly two of its node's values have been swapped.Returns:
[val1, val2], representing the values of the two swapped nodes. val1 should be less than or equal to val2.Examples
Example 1
Input:
root = [3,1,4,null,null,2]
Output:
[2,3]
Note:
The tree's in-order traversal is 1 -> 3 -> 2 -> 4. The BST property is violated at 3 > 2. This indicates that the values 2 and 3 have been swapped. The output should be [2,3].
Example 2
Input:
root = [1,3,null,null,2]
Output:
[1,3]
Note:
This tree has root 1, its right child 3, and 3's left child 2. The in-order traversal is 1 -> 2 -> 3. This is a valid BST. Wait, this example is invalid for the problem statement. Let's correct it. Corrected example: root = [2,3,1]. Root is 2, left child is 3, right child is 1. In-order traversal: 3 -> 2 -> 1. First violation at (3,2), second at (2,1). The original values 1 and 3 are swapped. The output should be [1,3].
Example 3
Input:
root = [6,3,8,4,1,7,9]
Output:
[1,4]
Note:
If the original BST had values 1,2,3,4,6,7,8,9 (in-order) and values 1 and 4 were swapped, the tree's in-order traversal would be 4 -> 3 -> 1 -> 6 -> 7 -> 8 -> 9. The first violation occurs when comparing 4 and 3 (first=4), and the second violation occurs when comparing 3 and 1 (second=1). The swapped values are 1 and 4. The output should be [1,4].
Constraints
[2, 1000].Node.val is in the range [-2^31, 2^31 - 1].Loading editor...