Frontend School

Recover Swapped Nodes in BST

DSA
medium

Recover Swapped Nodes in BST

Medium
Tree
Binary Search Tree
Inorder Traversal

Overview

Maintaining data integrity in large-scale systems is paramount. Consider a scenario where a critical Binary Search Tree (BST), used for indexing or sorted data retrieval, has been corrupted due to a rare data anomaly or a faulty maintenance operation. Specifically, exactly two nodes within the tree have had their values swapped, violating the BST property. Your task is to identify these misplaced nodes and restore the BST to its correct state without altering its structural integrity.

What you need to do / Task

Your primary goal is to implement a function that takes the root of a corrupted BST as input and rectifies it. You must:

  1. Identify the two nodes whose values have been swapped, causing the BST property violation.
  2. Swap their values back to their correct positions.
  3. The tree's structure (parent-child relationships) must remain unchanged; only node values should be modified.

Input & output

Input: root: A TreeNode | null, representing the root of the binary search tree where exactly two node values have been swapped.

Output: void. The function should modify the input tree in-place, correcting the swapped node values. No value should be returned.

Clarifications

  • Empty or single-node tree: For a swap to occur, the tree must contain at least two nodes. You can assume root will not be null and will have at least two nodes.
  • Exactly two swapped nodes: You are guaranteed that precisely two nodes' values are out of place. There won't be more or fewer than two swapped nodes.
  • Unique values: Node values are not necessarily unique.
  • Value vs. Node Swap: You are expected to swap the values of the two incorrect nodes, not their actual TreeNode objects or their positions in the tree structure.

Examples

1

Example 1

Input:

root = [1,3,null,null,2]

Output:

[1,2,null,null,3]

Note:

The original tree's inorder traversal would be [1, 3, 2]. The correct inorder traversal should be [1, 2, 3]. The values 3 and 2 are swapped. After correction, the tree becomes [1, 2, null, null, 3].

2

Example 2

Input:

root = [3,1,4,null,null,2]

Output:

[2,1,4,null,null,3]

Note:

The original tree's inorder traversal would be [1, 3, 2, 4]. The correct inorder traversal should be [1, 2, 3, 4]. The values 3 and 2 are swapped. After correction, the tree becomes [2, 1, 4, null, null, 3].

3

Example 3

Input:

root = [3,2,null,null,1]

Output:

[1,2,null,null,3]

Note:

The original tree's inorder traversal would be [2, 1, 3]. The correct inorder traversal should be [1, 2, 3]. The values 2 and 1 are swapped. After correction, the tree becomes [1, 2, null, null, 3].

Constraints

Constraints & assumptions

  • The number of nodes in the tree n is between 2 and 1000.
  • Node values (val) are integers in the range [-2^31, 2^31 - 1].
  • The tree structure itself is valid (e.g., no cycles, proper binary tree connections), only the BST property is violated by the swapped values.
  • Exactly two nodes' values have been swapped.

Out of scope

  • Handling more or fewer than two swapped nodes.
  • Reconstructing a completely broken tree where the structure is also invalid.
  • Rebalancing the tree after correction (not required).

What interviewers evaluate

  • Correctness: Accurately identifying and correcting the two swapped node values to restore the BST property.
  • Efficiency: Optimal time and space complexity for traversing the tree and performing the correction.
  • Code Quality: Clean, readable, and well-structured code with appropriate variable names and comments.
  • Problem-Solving: Ability to decompose the problem, identify the core issue (BST property violation), and apply appropriate data structures/algorithms (e.g., inorder traversal).

Loading editor...