Recover BST (Two Nodes Swapped)

Welcome back to CodeYourCraft! Today, we're diving into an interesting problem known as Recover BST (Binary Search Tree) - a scenario where two nodes in a Binary Search Tree have been swapped, and we need to find and restore the original order. Let's get started! 🎯

What is a Binary Search Tree (BST)?

A Binary Search Tree (BST) is a data structure where each node has at most two children (left and right). It follows the property that for every node, the left subtree's values are less than the node's value, and the right subtree's values are greater than the node's value. This property helps us perform efficient search, insert, and delete operations. 📝

The Problem: Two Nodes Swapped

Imagine a BST with the following structure:

Now, suppose two nodes are swapped: 8 and 11. The tree now looks like this:

Here, the BST property is violated because 11 appears in both the left and right subtrees of 10. Our goal is to find and restore the original order.

Recover BST: Solutions

There are two common methods to solve this problem: Morris Traversal and Inorder Recursive Traversal with two stack data structures. We'll explore both methods in detail.

Morris Traversal

Morris Traversal is an in-place, iterative algorithm for traversing a BST. It's particularly useful in this problem because it allows us to detect swapped nodes.

Morris Traversal Steps

Start from the root of the BST.
If the current node (curr) is null, we've reached the end of the traversal.
If curr is null, we visit the left child (prev).
If the left child (left) is not null, make prev the right child of left and set left as the current node. Skip this step if left is already being processed.
Visit prev.
After visiting prev, check if prev's inorder successor (the smallest node in the right subtree) exists. If it doesn't, prev is a swapped node.
If prev has a right child, set curr to the right child and go back to step 2.
If prev doesn't have a right child, set prev's right child to the current node (if not null) and set curr to the left child of the current node. Go back to step 2.

Morris Traversal Code Example

python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def findSwapped(root):
    prev = None
    curr = root

    while curr:
        if not curr.left:
            curr = curr.right
            continue

        prev = curr.left
        curr = curr.left
        while curr and curr != prev:
            curr = curr.right

        if not curr:
            print(f"Swapped nodes: {prev.key}, {curr.key}")
            prev.right = curr.left
            curr.left = prev
            curr = prev.right
        else:
            curr = curr.left

root = Node(10)
root.left = Node(8)
root.right = Node(12)
root.left.right = Node(4)
root.right.right = Node(11)

findSwapped(root)

Inorder Recursive Traversal with Two Stacks

This method involves using two stacks (inorderStack and recStack) and inorder traversal of the BST. The basic idea is to maintain the original order of the nodes while swapping nodes.

Inorder Recursive Traversal Steps

Perform inorder traversal of the BST using a helper function inorder(root, inorderStack).
In the helper function, push the current node (curr) onto recStack when visiting the left subtree.
If curr has been visited before, swap the top nodes from inorderStack and recStack.
When visiting the right subtree, pop the current node (curr) from inorderStack.
After the recursive call, pop the current node (curr) from inorderStack and push it onto recStack.
After processing all the nodes, swap the remaining nodes from inorderStack and recStack.

Inorder Recursive Traversal Code Example

python

def inorder(node, inorderStack):
    if node:
        inorder(node.left, inorderStack)
        inorderStack.append(node)
        visit(node)
        inorder(node.right, inorderStack)

def visit(node):
    recStack.append(node)
    if node.key == prev.key:
        print(f"Swapped nodes: {prev.key}, {node.key}")
        prev.key, node.key = node.key, prev.key

root = Node(10)
root.left = Node(8)
root.right = Node(12)
root.left.right = Node(4)
root.right.right = Node(11)

inorderStack = []
recStack = []
prev = None

inorder(root, inorderStack)

Quiz Time!

Wrapping Up

Today, we learned about the Recover BST problem and explored two methods to solve it: Morris Traversal and Inorder Recursive Traversal with two stack data structures. By understanding these techniques, you've taken a step closer to mastering BSTs and data structures in general. Keep practicing, and happy coding! 💡