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

Problem: Recover Binary Search Tree

Discover how to recover a binary search tree where two nodes have been mistakenly swapped. Learn to use constant space Morris inorder traversal to detect and fix violations in node order by swapping values, ensuring the tree remains structurally unchanged. This lesson helps you implement an efficient O(n) time and O(1) space solution for BST recovery.

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].

  • ...