Recover Binary Search Tree

MediumTreesbst

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the root of a binary search tree in which the values of **exactly two** nodes were swapped by mistake. Every other node holds the value it should. Repair the tree so it is a valid BST again. Do this by exchanging values only; the shape of the tree must stay exactly the same. Return the root of the repaired tree (it is serialized back to level order for grading). All node values are distinct. A plain approach stores the in-order sequence in O(n) space; as a follow-up, try to do it in O(1) extra space.

Examples

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
In-order reads 3, 2, 1. Swapping 1 and 3 gives the sorted order 1, 2, 3.
Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
In-order reads 1, 3, 2, 4. The out-of-place pair is 3 and 2.

Constraints

  • 2 <= number of nodes <= 1000
  • -2^31 <= Node.val <= 2^31 - 1
  • All values are distinct
  • Exactly two nodes have had their values swapped

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bst problems