Merge two BST 's
PROBLEM :
Given two BST, Your task is to complete the function merge which prints the elements of both BSTs in sorted form.
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains three lines. The first line of each test case contain's an integer N and M denoting the size of the two BST's. Then In the next two line are space separated values of the two BST's.
Output:
The function should print the elements of both BST's in sorted form.
Constraints:
1<=T<=100
1<=N,M<=100
Example(To be used only for expected output):
Input:
2
3 3
1 33 4
6 7 1
2 2
1 6
9 2
Output:
1 1 4 6 7 33
1 2 6 9
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
/* The structure of Node is
struct Node {
int data;
Node * right, * left;
};*/
/*You are required to complete below method */
int size_tree(Node *) ;
void store_array(Node *,int [],int *) ;
void merge(Node *root1,Node *root2)
{
int s1,s2 ;
s1=size_tree(root1) ;
s2=size_tree(root2) ;
int arr[s1+s2] ;
int i,s ;
s=0 ;
store_array(root1,arr,&s) ;
store_array(root2,arr,&s) ;
sort(arr,arr+s1+s2) ;
for(i=0;i<s1+s2;i++)
cout<<arr[i]<<" " ;
}
int size_tree(Node *root)
{
if(root==NULL)
return 0 ;
return size_tree(root->left)+size_tree(root->right)+1 ;
}
void store_array(Node *root,int arr[],int *curr)
{
if(root==NULL)
return ;
store_array(root->left,arr,&(*curr)) ;
arr[(*curr)++]=root->data ;
store_array(root->right,arr,&(*curr)) ;
}
---------------------------------------------------------------------------------
Given two BST, Your task is to complete the function merge which prints the elements of both BSTs in sorted form.
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains three lines. The first line of each test case contain's an integer N and M denoting the size of the two BST's. Then In the next two line are space separated values of the two BST's.
Output:
The function should print the elements of both BST's in sorted form.
Constraints:
1<=T<=100
1<=N,M<=100
Example(To be used only for expected output):
Input:
2
3 3
1 33 4
6 7 1
2 2
1 6
9 2
Output:
1 1 4 6 7 33
1 2 6 9
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
/* The structure of Node is
struct Node {
int data;
Node * right, * left;
};*/
/*You are required to complete below method */
int size_tree(Node *) ;
void store_array(Node *,int [],int *) ;
void merge(Node *root1,Node *root2)
{
int s1,s2 ;
s1=size_tree(root1) ;
s2=size_tree(root2) ;
int arr[s1+s2] ;
int i,s ;
s=0 ;
store_array(root1,arr,&s) ;
store_array(root2,arr,&s) ;
sort(arr,arr+s1+s2) ;
for(i=0;i<s1+s2;i++)
cout<<arr[i]<<" " ;
}
int size_tree(Node *root)
{
if(root==NULL)
return 0 ;
return size_tree(root->left)+size_tree(root->right)+1 ;
}
void store_array(Node *root,int arr[],int *curr)
{
if(root==NULL)
return ;
store_array(root->left,arr,&(*curr)) ;
arr[(*curr)++]=root->data ;
store_array(root->right,arr,&(*curr)) ;
}
---------------------------------------------------------------------------------
Comments
Post a Comment