hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Merge Two BSTs


  • Approach:

    1. The first we should do is traverse both the tree and insert the elements into a list without NULL nodes.

    2. Sort the array in increasing order.

    3. Now again build another BST with the sorted list.

    4. Follow this process: Sorted Array to Balanced BST


  • Time and Space Complexity:

    • Time Complexity: O(NlgN)

    • Space Complexity: O(N) + Auxilary Stack.


Code [C++]

#include <bits/stdc++.h>

/*************************************************************

Following is the Binary Tree node structure:


class TreeNode{


public :

int data;

TreeNode *left;

TreeNode *right;


TreeNode(int data) {

this -> data = data;

left = NULL;

right = NULL;

}


~TreeNode() {

if (left){

delete left;

}


if (right){

delete right;

}

}

};


*************************************************************/


void traverseBST(TreeNode<int> * root, vector<int> & numbers){

if(root == NULL) return;

traverseBST(root->left, numbers);

if(root->data != -1)

numbers.push_back(root->data);

traverseBST(root->right, numbers);

}


TreeNode<int> * buildBst(vector<int> & numbers, int start, int end){

if(start > end) return NULL;

int mid = (start + end) / 2;

TreeNode<int> * root = new TreeNode <int> (numbers[mid]);

root->left = buildBst(numbers, start, mid - 1);

root->right = buildBst(numbers, mid + 1, end);

return root;

}


TreeNode<int> *mergeBST(TreeNode<int> *root1, TreeNode<int> *root2){

vector<int>numbers;

traverseBST(root1, numbers);

traverseBST(root2, numbers);

sort(numbers.begin(), numbers.end());

TreeNode<int>* newRoot = buildBst(numbers, 0, numbers.size()-1);

return newRoot;

}