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

ID: 3822195 • 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 ifthe 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.

Explanation / Answer

bool sameValueTree(TreeNode *node1, TreeNode *node2, int *&array1, int *&array2)
{
   // find the inorder traversal of 1st TreeNode
   index1++;
   inorderTraversal1(node1, array1);

   // find the inorder traversal of 2nd TreeNode
   inorderTraversal2(node2, array2, index2+1);

   // index1 and index2 will have the size of the Tree 1 and Tree 2
   // respectively after the inorder traversal.

   if(index1 != index2)
       return false;

   // if the size of both the arrays are same, then we can
   // proceed to compare the elements.

   // logic for comparison is:
   // if we have 4 elements in array1 and 4 elements in array2,
   // then number of matchCount = 4.

   // matchCount is number of matches between 2 arrays.
   int matchCount = 0;

   for (int i=0;i<index1;++i)
   {
       for (int j=0;j<index2;++j)
       {
           if (array1[i] == array2[j])
           {
               matchCount++;
           }
       }
   }

   if (index1 == matchCount)
       return true;

   else
       return false;
}

// two similar inorder traversal functions are given here because
// we need to use the global index1 and index2 variables to get the
// size of the trees.

void inorderTraversal1(TreeNode *node, int *&array)
{
if (node == NULL)
return;

/* first recur on left child */
inorderTraversal1(node->left);

array[index1++] = node->data;

/* now recur on right child */
inorderTraversal1(node->right);
}

void inorderTraversal2(TreeNode *node, int *&array)
{
if (node == NULL)
return;

/* first recur on left child */
inorderTraversal2(node->left);

array[index2++] = node->data;

/* now recur on right child */
inorderTraversal2(node->right);
}

Navigate

Write a C++ function that returns True if two trees are structurally identical.(

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