Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms

Problem: Recover Binary Search Tree

Explore how to recover a binary search tree where exactly two nodes have been swapped by mistake. Learn to detect violations during an inorder traversal and restore the BST using a constant space Morris traversal technique. This lesson helps you build an efficient solution without extra memory overhead.

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 O(n)O(n) space is relatively straightforward. Can you devise a constant O(1)O(1) space solution?

Constraints:

  • The number of nodes in the tree is in the range [2,1000][2, 1000].

  • ...