Problem: Recover Binary Search Tree
Discover how to recover a binary search tree when two nodes are incorrectly swapped by applying Morris inorder traversal. Learn to detect violations in the BST's sorted order, identify misplaced nodes, and restore the correct structure using constant space. This lesson helps you implement an efficient, non-recursive solution that optimizes space without altering the tree's structure.
We'll cover the following...
Statement
You are given the root of a binary search tree (BST) in which the values of exactly two nodes have been swapped by mistake. Restore the BST to its correct form without altering the structure of the tree.
Note: A solution using
space is relatively straightforward. Can you devise a constant space solution?
Constraints:
The number of nodes in the tree is in the range
. ...