Problem: Recover Binary Search Tree
Explore how to recover a binary search tree where two nodes have been swapped by mistake. Learn to identify the swapped nodes using Morris inorder traversal, which allows tree traversal with constant space. Understand how to detect violations in the sorted order of inorder traversal and swap the incorrect nodes back to restore the BST.
We'll cover the following...
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
...