# Thread: Given two binary search trees, write a function which.....

1. ## Given two binary search trees, write a function which.....

Hi everyone!

I'm having some troubles with the definition of a function.
Here there is the exercise:

"Given two Binary Search Trees, T1 and T2, which contain float values, write a function that create a new Binary Search Tree, which has in his nodes the common elements among T1 and T2".

This were my thoughts:

-I create a function which put in an array the elements of a Binary Search Tree (I called it "visitcopy");
-I create two arrays, A1 and A2, for the values of my T1 and T2;
-I create a doublepointer and a pointer to a structured data "struct btree" (this is my new Tree);
-With a for cycle, I make a comparison between the two arrays and everytime I find a common element, I add a node in my new Binary Search Tree.

Here there is my code:

Code:
```void newcommon (struct btree *p, struct btree *punt, int first, int second){

//first and second are the number of nodes of the first and second tree

float *A;
A= (float*)calloc(first, sizeof(float));
int *k;
int u=-1;
k=&u;
visitcopy(p, A, k);

float *B;
B=(float*)calloc(second, sizeof(float));
visitcopy(punt, B, k);

struct btree **doublepointer;
struct btree *pointer;
doublepointer= &pointer;
init(doublepointer);

int i,j;
for (i=0;i<first;i++){
for (j=0;j<second;j++){
if (A[i]==B[j]){

insert_inorder(doublepointer, A[i]);
printf ("\n\n new node created in the new tree %f\n\n", A[i]);

}
}
}
}

void visitcopy (struct btree * ptr, float *E, int *i) {

if (ptr != NULL) {

visitcopy(ptr->left_ptr, E, (int)(*i)++);
E[(*i)]=(ptr->value);
printf ("\n\n\n  the value number %d of the array is %f  \n\n\n",(*i), E[(*i)]);

visitcopy(ptr->right_ptr, E, (int)(*i)++);
}
}```

From the debugging, I think that the main problem is in visitcopy, but there are also one or more mistake in the main function.

2. Originally Posted by letthem
-I create a function which put in an array the elements of a Binary Search Tree (I called it "visitcopy");
-I create two arrays, A1 and A2, for the values of my T1 and T2;
-I create a doublepointer and a pointer to a structured data "struct btree" (this is my new Tree);
-With a for cycle, I make a comparison between the two arrays and everytime I find a common element, I add a node in my new Binary Search Tree.
Don't do that. Binary search trees can be traversed and searched. Traverse over one binary search tree and search the other for its elements, inserting into a third binary search tree each element's value for which there is a match.

If you really want to go with two arrays, then you might as well assume that the binary search trees have degraded into linked lists, so you sort each array then do a single pass to extract the common values. However, you need to take care when constructing the new binary search tree that you don't create one that degrades into a linked list.

3. Originally Posted by laserlight
Traverse over one binary search tree and search the other for its elements, inserting into a third binary search tree each element's value for which there is a match.
Hello Laserlight!

Unfortunately, I'm not able to do that.
I know how to do visit a binary search tree (in many ways).
I know how to search a value in a binary search tree.
But I'm not able (at all) to do what you wrote.

May you let me see how you would do that please?

4. Originally Posted by letthem
I know how to search a value in a binary search tree.
Write a function to do this. The function will return true if the value is found, otherwise it will return false.

You can then write another function to visit one of the binary trees and call that function.

5. Originally Posted by laserlight
Write a function to do this. The function will return true if the value is found, otherwise it will return false.

You can then write another function to visit one of the binary trees and call that function.
Hello Laserlight!

Here there is the function which search a specific value in a Binary Search Tree:

Code:
```Booleansearch(structbtree* ptr, floattarget) {
if(ptr != NULL) { //It's not a leave
if(ptr->value== target) { //FOUND
returnTRUE;}
else{ // NONtrovato
if(target < ptr->value)// vaia sx
returnsearch(ptr->left_ptr,target);
else// oppurevaia dx
returnsearch(ptr->right_ptr,target);
}
}
else
return FALSE;}```
Let me see if I understood what you said.
You're suggesting to:
1)visit the first binary search tree;
2)use the search function in the second binary search tree for every value of the first binary search tree ;
3) if the search function give as result TRUE, create a new node in the third tree.

Am I correct?

6. Yes.