Fix a BST with two misplaced keys

Q: Fix a BST with two misplaced keys

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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(

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.

Fix a BST with two misplaced keys

Overview

Comments (0)