DSA interview question

Recover a BST with Two Swapped Nodes

Hard · Algorithms · Topics: bst, inorder, recursion

The problem

A buggy migration swapped the values of exactly two nodes in a BST, silently breaking lookups. Recover the tree without changing its structure. In a correct BST, the inorder sequence is strictly increasing. Swapping two values creates either one "drop" (if the two nodes are adjacent in inorder) or two drops. The first swapped node is the larger value at the first drop, and the second swapped node is the smaller value at the last drop. Swap their values back.

Example: [1, 3, null, null, 2] → [3, 1, null, null, 2].

Function signature

void recoverTree(TreeNode* root);  // swaps the two misplaced values back in place

Test cases

Input (level order)	Output (level order)	Explanation
`[1, 3, null, null, 2]`	`[3, 1, null, null, 2]`	Inorder 3 2 1 has two drops
`[3, 1, 4, null, null, 2]`	`[2, 1, 4, null, null, 3]`	Inorder 1 3 2 4 has one drop
`[2, 3, 1]`	`[2, 1, 3]`
`[1, 2]`	`[2, 1]`
`[5, 8, 3, 1, 4, 7, 9]`	`[5, 3, 8, 1, 4, 7, 9]`	8 and 3 were swapped; inorder 1 8 4 5 7 3 9 has two drops

(Confirm: exactly two nodes were swapped; keys are distinct; only values change, never links.)

How interviewers phrase it

"You are given the root of a BST where the values of exactly two nodes were swapped by mistake. Recover the tree without changing its structure" (LeetCode 99), with an O(1)-space follow-up.

Clarifying questions to ask

Exactly two nodes swapped? (Yes.)
May I only swap values, not relink? (Yes.)
Is O(h) space acceptable, or must it be O(1)? (O(h) first; Morris for O(1).)

Follow-ups to expect

"Why look at inorder?"
"Why the first node of the first drop and the second node of the last drop?"
"Brute force?"
"O(1) space?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview