Frontend School

Identify Swapped Nodes in a Malformed BST

DSA
medium

Identify Swapped Nodes in a Malformed BST

Medium
Tree
Binary Search Tree
In-order Traversal

Overview

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.

What you need to do / Task

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:

  1. Traverse the given binary tree, which was originally a valid BST but now has exactly two node values swapped.
  2. Identify the values of these two nodes.
  3. Return an array containing these two values in ascending order.

Input & output

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:

  • An array of two numbers, [val1, val2], representing the values of the two swapped nodes. val1 should be less than or equal to val2.

Clarifications

  • The problem guarantees that exactly two nodes have had their values swapped.
  • All node values in the original (correct) BST were unique.
  • The tree will always contain at least two nodes.

Examples

1

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].

2

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].

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

Constraints & assumptions

  • The number of nodes in the tree is in the range [2, 1000].
  • Node.val is in the range [-2^31, 2^31 - 1].
  • All values in the original (correct) BST were unique.
  • Exactly two nodes have had their values swapped.

Out of scope

  • You do not need to restore the BST to its correct state; only identifying the values of the swapped nodes is required.
  • You do not need to handle cases where more or fewer than two nodes are swapped.
  • You do not need to handle cases where the original BST contained non-unique values.

What interviewers evaluate

  • Correctness: Accurately identifies the two swapped node values.
  • Efficiency: Optimal time and space complexity for the given constraints.
  • Algorithmic Understanding: Demonstrates a clear understanding of BST properties and how violations manifest.
  • Code Quality: Writes clean, readable, and well-structured code.

Loading editor...