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)) ;
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )