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

Problem: Recover Binary Search Tree

Understand how to identify and correct two swapped nodes in a binary search tree without changing its structure. Explore Morris inorder traversal to achieve an efficient O(1) space solution by detecting violations in the inorder sequence and swapping misplaced nodes, enhancing your skills in tree traversal and problem-solving.

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

  • ...