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

Problem: Recover Binary Search Tree

Understand how to recover a binary search tree after two nodes are mistakenly swapped. Explore the use of Morris inorder traversal to find and fix violations without extra space, improving your skills in tree algorithms and space optimization.

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

  • ...