Merge Two BSTs 🎯

Welcome to our deep dive into the exciting world of Merging Two Binary Search Trees (BSTs)! In this tutorial, we'll learn:

What are Binary Search Trees (BSTs)?
Why do we merge two BSTs?
The step-by-step process to merge two BSTs
Two complete, working examples with explanations
A quiz to reinforce your understanding

Let's get started!

Binary Search Trees (BSTs) 📝

A Binary Search Tree (BST) is a type of data structure that organizes data in a hierarchical tree-like structure. It's a versatile data structure used in various applications due to its efficient search, insert, and delete operations.

Each node in a BST has a maximum of two children: the left child and the right child.
The left child contains keys smaller than the parent, while the right child contains keys greater than the parent.

💡 Pro Tip: BSTs can be implemented using various programming languages, including Python, Java, and C++.

Merging Two BSTs 💡

Merging two BSTs is a useful operation when dealing with multiple trees in a real-world application. For example, during a database merge, merging BSTs can help efficiently combine data from multiple sources.

The process of merging two BSTs involves traversing both trees simultaneously and combining their nodes to form a single BST.

Merging Two BSTs: Step-by-step 📝

Initialize an empty BST, which will serve as the merged tree.
Traverse both BSTs in an In-Order (Left - Root - Right) fashion.
For each node encountered in the traversal, insert the node into the empty merged BST.
Continue the traversal until both trees are fully merged.

Example 1: Merging Two BSTs in Python ✅

Let's take two simple BSTs:

python

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

# BST 1
root1 = Node(50)
root1.left = Node(30)
root1.right = Node(70)
root1.left.left = Node(20)
root1.left.right = Node(40)
root1.right.right = Node(80)

# BST 2
root2 = Node(25)
root2.left = Node(10)
root2.right = Node(65)
root2.left.left = Node(5)
root2.left.right = Node(22)
root2.right.left = Node(75)

Now, let's merge these two BSTs:

python

def merge(root1, root2):
    if not root1:
        return root2
    if not root2:
        return root1

    if root1.val < root2.val:
        root1.right = merge(root1.right, root2)
        root1 = merge(root1, root2.left)
    else:
        root2.left = merge(root1, root2.left)
        root2 = merge(root2.right, root1)

    return root1 if root1 else root2

# Merged BST
merged_root = merge(root1, root2)

Example 2: Merging Two BSTs in Java ✅

Here's an example of merging two BSTs in Java:

java

class Node {
    int key;
    Node left, right;

    Node(int item) {
        key = item;
        left = right = null;
    }
}

// BST 1
Node root1 = new Node(50);
root1.left = new Node(30);
root1.right = new Node(70);
root1.left.left = new Node(20);
root1.left.right = new Node(40);
root1.right.right = new Node(80);

// BST 2
Node root2 = new Node(25);
root2.left = new Node(10);
root2.right = new Node(65);
root2.left.left = new Node(5);
root2.left.right = new Node(22);
root2.right.left = new Node(75);

// Merge BSTs
Node merged_root = merge(root1, root2);

The merge() method in Java is implemented similar to the Python example:

java

Node merge(Node root1, Node root2) {
    if (root1 == null)
        return root2;
    if (root2 == null)
        return root1;

    if (root1.key < root2.key) {
        root1.right = merge(root1.right, root2);
        root1.left = merge(root1.left, root2.left);
        return root1;
    } else {
        root2.left = merge(root1, root2.left);
        root2.right = merge(root1.right, root2.right);
        return root2;
    }
}

Quiz 💡

Now that you've learned about merging two BSTs, go ahead and practice on your own with different BSTs to consolidate your understanding! Happy coding! 🚀