Merge two BSTs with limited extra space

Introduction 🥷

A BST or binary search tree is a tree in which every node in the left subtree is smaller than the root node, and every node in the right subtree is greater than the root node. This property holds for every node present in the BST.

A BST is a balanced BST when the height difference for all the nodes present in the tree is not more than 1.
 

In this blog, we will discuss a coding problem in which we are given two balanced BST and we have to merge them into one.

Problem Statement 🧾

Ninja has given you two different balanced BSTs. Your task is to merge two balanced BSTs into one without using much extra space.

Sample Examples🧐

Input

Output

Explanation

After merging both of the balanced BST we get the above tree as our output.

Approach 🧑‍💻

We can use the Iterative inorder traversal. For two BSTs, we utilize two auxiliary stacks. Every time we obtain a smaller element from any of the trees, we store it because we must obtain the components in the sorted form. The element is pushed back to the stack for the following iteration if it is greater.
 

In the below approach while merging both of the BSTs, we are creating a sorted array of nodes we can use this sorted array to construct a balanced BST. To know more about this have a look at the approach explained in this blog.

Convert a normal BST to a Balanced BST🧐

Algorithm

1. Start
    
2. Create an array to store results.
    
3. Create two stacks s1 and s2.
    
4. Check tree1, tree2, s1, and s2 if any of these has any node present repeat the below process.
   
   
   1. While tree1 is not null keep on pushing the left-most node into the s1 stack.
       
   2. While tree2 is not null keep on pushing the left-most node into the s2 stack. 
       
   3. If the top element of the s1 is smaller than the top element of s2 then push it into the result vector and change the root1 value to right node of s1’s top element.
       
   4. If the top element of s1 is greater than the top element of s2 then push the top element of stack s2 into the result vector and change the root2 value to the right node of s2’s top element.
       
5. Exit

Implementation in C++ 🧑‍💻

#include <bits/stdc++.h>
using namespace std;

// node class
class Node
{
public:
    int val;
    Node *left, *right;

    Node(int val)
    {
        this->val = val;
        left = right = nullptr;
    }
};

// returns the vector array containing merged BSTs
vector<int> mergeTwoBST(Node *root1, Node *root2)
{

    vector<int> result;

    // holds the node for first and second BST
    stack<Node *> stck1, stck2;

    // run the loop until all of the nodes are not explored.
    while (root1 || root2 || !stck1.empty() || !stck2.empty())
    {

        // pushing all of the left-most nodes of first BST
        // into our stack1
        while (root1)
        {
            stck1.push(root1);
            root1 = root1->left;
        }

        // pushing all of the left-most nodes of second BST
        // into our stack2
        while (root2)
        {
            stck2.push(root2);
            root2 = root2->left;
        }

        // pushing the elements into our result vector accordingly
        if (stck2.empty() || (!stck1.empty() && stck1.top()->val <= stck2.top()->val))
        {
            root1 = stck1.top();
            stck1.pop();
            result.push_back(root1->val);
            root1 = root1->right;
        }
        else
        {
            root2 = stck2.top();
            stck2.pop();
            result.push_back(root2->val);
            root2 = root2->right;
        }
    }

    // returning the result.
    return result;
}

/* Driver program to test above functions */
int main()
{

    // tree 1
    Node *root1 = new Node(5);
    root1->left = new Node(3);
    root1->right = new Node(7);

    // tree 2
    Node *root2 = new Node(12);
    root2->left = new Node(10);
    root2->right = new Node(20);
    root2->left->right = new Node(11);
    root2->right->right = new Node(40);

    // Print sorted Nodes of both trees
    vector<int> ans = mergeTwoBST(root1, root2);
    for (auto it : ans)
        cout << it << " ";
    cout << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

3 5 7 10 11 12 20 40 

Time Complexity ⌛

The time complexity of the above program is O(m+n)  as we are iteratively traversing both of the balanced BST. m and n represent the total number of nodes present in our BSTs respectively.
 

Space Complexity 🚀

We are using two different stacks to store the nodes. However, at any point in time, the maximum number of elements present in the stack would be equal to the depth of our BST as we are only pushing the left-most node of the tree. So, the space complexity of our program is O(height of tree1 + height of tree2).

Check out this array problem - Merge 2 Sorted Arrays