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
Problem: Merge Two BSTs
Problem Link: https://www.codingninjas.com/codestudio/problems/h_920474
Approach:
The first we should do is traverse both the tree and insert the elements into a list without NULL nodes.
Sort the array in increasing order.
Now again build another BST with the sorted list.
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;
}