Fix a BST with two misplaced keys
Company: TikTok
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given the root of a binary search tree in which exactly two nodes’ keys were accidentally swapped. Restore the tree so that its in-order traversal is strictly non-decreasing, without changing the tree’s structure. Aim for O(n) time and O(
1) extra space; discuss an approach that does not use recursion or an explicit stack. Describe how you would detect the misplaced nodes, handle both adjacent and non-adjacent violations, and analyze time/space complexity.
Quick Answer: This question evaluates understanding of binary search trees, in-order traversal invariants, and in-place detection and correction of two swapped keys without altering tree structure.