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

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 sameValueTree() is called on the following two trees:

1)

3

/

2 4

2)

4

/

3

/

2

It should return True. However, if sameValueTree() is called on the following two trees:

3)

3

/

2 4

4)

4

/

3 5

/

2

It should return False.

Few notes to help you out:

1) Function header should be: bool sameValueTree(TreeNode *node1, TreeNode *node2, int *& array1, int *& array2 )

2) The node structure is: struct TreeNode{ int key; TreeNode *left; TreeNode *right; };

3) The two arrays are passed to the function from main and are initialized as follow: int * array1 = NULL; int * array2 = NULL;

4) You can use the function sizeTree() as a helper function. This was implemented for you and its defined as follow: int sizeTree(TreeNode * node);

5) To help you with your implementation you can use the following global variables already initialized for you:

int index1 = -1; // index to access array1

int index2 = -1; // index to access array2

int treeSize = -1; // once you find the size of the 2 BSTs assign it to this variable

bool isEqual = true; // change this value accordingly and return it from sameValueTree()

Hints: - populate the array correctly because there are test cases that will check your arrays - you may want to find out the size of each BST first. - handle the cases where the size of the 2 trees are not the same - you may want to choose a specific searching algorithm already seen in class to store the values in ascending order - remember to handle the base case (i.e. when counter1=counter2=Null) if you are going to use recursion. - You do not have to handle the case of repeated numbers in a tree.

For example

5)

3

/

2 4

6)

4

/

3 4

/

2

This should still return False.

Explanation / Answer

Ans:The below is the c++ program explained with comments.

/* program */

//bits/stdc++.h

#include <bits/stdc++.h>

//namespace

using namespace std;

//Tree Node

// struct

struct Node

{

//data

int data;

// left_right

struct Node *left, *right;

};

// first finds height (bool)

bool sameValueTree(Node *root1, Node *root2)

{

// Returns the true(if_empty)

if (!root1 && !root2) return true;

// 1 empty nd other not empty

if (!root1 || !root2) return false;

// creates empty q1 q2

queue<Node *> q1, q2;

// engues the roots

// root1

q1.push(root1);

// q2

q2.push(root2);

// while

while (!q1.empty() && !q2.empty())

{

// front node compares

Node *n1 = q1.front();

/q2

Node *n2 = q2.front();

// if cond

if (n1->data != n2->data)

// returns false

return false;

// removes (pop)

q1.pop(), q2.pop();

// engues left

if (n1->left && n2->left)

{

// q1

q1.push(n1->left);

//q2

q2.push(n2->left);

}

//1_left_child empty and second isnt

else if (n1->left || n2->left)

//returns false   

return false;

// for right-child

if (n1->right && n2->right)

{

// push q1

q1.push(n1->right);

// push q2

q2.push(n2->right);

}

// else if

else if (n1->right || n2->right)

// returns false

return false;

}

// returns_true

return true;

}

// func to create tree

// node

Node* newNode(int data)

{

// temp

Node *temp = new Node;

// data

temp->data = data;

// null left_right

temp->left = temp->right = NULL;

// returns

return temp;

}

//test using the Driver_program

main()

int main()

{

// root1

Node *root1 = newNode(1);

//left

root1->left = newNode(2);

//right

root1->right = newNode(3);

//left_left

root1->left->left = newNode(4);

// left_right

root1->left->right = newNode(5);

// root-2

Node *root2 = newNode(1);

//LEFT

root2->left = newNode(2);

//right

root2->right = newNode(3);

// left-left

root2->left->left = newNode(4);

left-right

root2->left->right = newNode(5);

//cout yes-no

sameValueTree(root1, root2)? cout << "Yes"

: cout << "No";

// return

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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