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

Problem: Recover Binary Search Tree

Understand how to identify and correct two swapped nodes in a binary search tree without altering its structure. Learn to implement Morris inorder traversal for efficient, constant space recovery while ensuring the tree maintains its sorted order.

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

  • ...