Katkat
Back

Fix a BST with two misplaced keys

TikTokMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Fix a BST with two misplaced keys states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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.