Write a C++ function that returns True if two trees have the same values (they a

ID: 3851382 • Letter: W

Question

Write a C++ function that returns True if two trees have the same values (they are made of nodes with the same values.) It should return True if the trees have te same values or False otherwise. The function takes four arguments: treenode of tree1, treenode of tree2, and two arrays. Note that two trees can have the same values but not have the same structure. To successfully code this function up you will have to populate two arrays in ascending order with the values you find when traversing the two trees. For example: if samevalueTree0 is called on the following two trees: It should return True. However, if samevalueTree0 is called on the following two trees: It should return False. Few notes to help you out: 1) Function header should be: bool samevalueTree(TreeNode *node1, TreeNode *node2, int & array 1, int *& array2);

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int SameValueTree(int a[], int b[], int a1 , int b1)
{
int i=0,j=0;
   int flag = 1;
   for(i=0,j=0;i<a1 && j<b1 ;i++,j++){
       if(a[i] != b[j]){
           flag = 0;
           break;
       }
   }
   return flag;
}

int AddToArray(struct node *node, int arr[], int i)
{
if(node == NULL)
return i;

arr[i] = node->data;
i++;
if(node->left != NULL)
i = AddToArray(node->left, arr, i);
if(node->right != NULL)
i = AddToArray(node->right, arr, i);

return i;
}

int sizeTree(struct node *n)
{
int c = 1;

if (n == NULL)
return 0;
else
{
c += sizeTree(n->left);
c += sizeTree(n->right);
return c;
}
}

void sort(int m, int x[ ])
{
int i, j, t;

for(i = 1; i <= m-1; i++)
for(j = 1; j <= m-i; j++)
if(x[j-1] >= x[j])
{
t = x[j-1];
x[j-1] = x[j];
x[j] = t;
}
}

int main()
{
struct node *tree1 = newNode(2);
struct node *tree2 = newNode(2);
tree1->left = newNode(3);
tree1->right = newNode(4);
tree1->left->left = newNode(5);
tree1->left->right = newNode(6);

tree2->left = newNode(3);
tree2->right = newNode(4);
tree2->left->left = newNode(5);
tree2->left->right = newNode(6);
   int a = sizeTree(tree1);
   int b = sizeTree(tree2);

   if(a!=b)
       printf("Trees are not identical. ");
   else{
   int arr1[a];
   int arrb[b];

   AddToArray(tree1,arr1,0);
   AddToArray(tree2,arrb,0);

   sort(a,arr1);
   sort(b,arrb);

if(SameValueTree(arr1, arrb, a, b)==1)
printf("Both tree are identical. ");
else
printf("Trees are not identical. ");

   }
return 0;
}

Navigate

Write a C++ function that returns True if two trees have the same values (they a

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Write a C++ function that returns True if two trees have the same values (they a

Question

Explanation / Answer

Related Questions

Navigate