algoadvance

The problem “Recover Binary Search Tree” involves correcting a binary search tree (BST) in which two of the nodes had their values swapped by mistake. The goal is to identify the two nodes that were swapped and recover the BST by swapping their values back to their correct positions.

Input:

Output:

For example:

Input: [1,3,null,null,2]
Tree structure: 
    1
   /
  3
   \
    2

Output: [3,1,null,null,2]
Tree structure corrected to:
    3
   /
  1
   \
    2

Clarifying Questions

  1. Can I assume that the given tree is always a valid BST except for the two swapped nodes?
  2. Is it guaranteed that there are exactly two nodes that were swapped?
  3. Can the tree contain duplicate values, or are all values unique?

Strategy

  1. In-order Traversal: Perform an in-order traversal of the tree. Since in-order traversal of a BST should produce a sorted sequence, any deviation from the sorted order indicates the swapped nodes.
  2. Identify Nodes: Track the nodes which are out of order. There will be exactly two such nodes in a pair. The first occurrence of disorder will give the first node, and the second occurrence will give the second node (or the last correct node followed by the first incorrect one).
  3. Recover Tree: Once we have identified the two nodes, swap their values to correct the BST.

Code

```python class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

class Solution: def recoverTree(self, root: TreeNode) -> None: # Variables to keep track of the two nodes to be swapped self.first = self.second = self.prev = None

    def inorder(node: TreeNode):
        if node is None:
            return
        
        # In-order traversal: left subtree
        inorder(node.left)
        
        # Identify the misplaced nodes
        if self.prev and self.prev.val > node.val:
            if not self.first:
                self.first = self.prev
            self.second = node

        self.prev = node
        
        # In-order traversal: right subtree
        inorder(node.right)

    # Perform the in-order traversal
    inorder(root)

    # Swap the values of the two nodes to correct the tree
    if self.first and self.second:
        self.first.val, self.second.val = self.second.val, self.first.val

Time Complexity

  1. In-order Traversal: O(n), where n is the number of nodes in the tree.
  2. Space Complexity: O(h), where h is the height of the tree (due to recursion stack). For a balanced tree, h = O(log n). In the worst case (skewed tree), h = O(n).

Let’s implement the provided code to solve this problem efficiently.

Try our interview co-pilot at AlgoAdvance.com