### Create a function called isSameTree

Create a function called bool isSameTree that will take an argument of a tree. It will return a true if the argument is the equivalent tree or return false if the the two tree's are not equivalnet. I have written all the code for class except the isSameTree function. Could someone guide me on how I compare the trees. I have include a file called BinaryTee.cpp in this.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222`` ``````#include "BinaryTree.h" #include #include void BinaryTree::destroySubTree(TreeNode*& nodePtr) { if (nodePtr) { if (nodePtr->left) destroySubTree(nodePtr->left); if (nodePtr->right) destroySubTree(nodePtr->right); delete nodePtr; nodePtr = nullptr; } } void BinaryTree::insert(TreeNode*& nodePtr, TreeNode*& newNode) { if (nodePtr == nullptr) nodePtr = newNode; else if (newNode->value < nodePtr->value) insert(nodePtr->left, newNode); else insert(nodePtr->right, newNode); } void BinaryTree::insert(int number) { TreeNode* newNode = new TreeNode; newNode->value = number; newNode->right = newNode->left = nullptr; // Insert newNode into tree insert(root, newNode); } void BinaryTree::displayInOrder(TreeNode* nodePtr) { if (nodePtr) { displayInOrder(nodePtr->left); cout << nodePtr->value << endl; displayInOrder(nodePtr->right); } } void BinaryTree::displayInOrderWithLevel(TreeNode* nodePtr, int level) { if (nodePtr) { displayInOrderWithLevel(nodePtr->left, level + 1); for (int index = 0; index < level; index++) cout << "\t"; cout << nodePtr->value << endl; displayInOrderWithLevel(nodePtr->right, level + 1); } } void BinaryTree::displayPostOrder(TreeNode* nodePtr) { if (nodePtr) { displayPostOrder(nodePtr->left); displayPostOrder(nodePtr->right); cout << nodePtr->value << endl; } } void BinaryTree::displayPreOrder(TreeNode* nodePtr) { if (nodePtr) { cout << nodePtr->value << endl; displayPreOrder(nodePtr->left); displayPreOrder(nodePtr->right); } } void BinaryTree::displayInOrder() { displayInOrder(root); } void BinaryTree::displayInOrderWithLevel() { displayInOrderWithLevel(root, 0); } void BinaryTree::displayPreOrder() { displayPreOrder(root); } void BinaryTree::displayPostOrder() { displayPostOrder(root); } bool BinaryTree::search(int number) { TreeNode* nodePtr = root; while (nodePtr) { if (nodePtr->value == number) return true; else if (number < nodePtr->value) nodePtr = nodePtr->left; else nodePtr = nodePtr->right; } return false; } void BinaryTree::deleteNode(int number, TreeNode*& nodePtr) { if (number < nodePtr->value) deleteNode(number, nodePtr->left); else if (number > nodePtr->value) deleteNode(number, nodePtr->right); else makeDeletion(nodePtr); } void BinaryTree::makeDeletion(TreeNode*& nodePtr) { // Define a temporary pointer to use in reattaching the left subtree TreeNode* tempNodePtr = nullptr; if (nodePtr == nullptr) cout << "Cannot delete an empty node" << endl; else if (nodePtr->right == nullptr) // reattach the left child { tempNodePtr = nodePtr; nodePtr = nodePtr->left; delete tempNodePtr; } else if (nodePtr->left == nullptr) // reattach the right child { tempNodePtr = nodePtr; nodePtr = nodePtr->right; delete tempNodePtr; } // if the node has two children else { // move one node to the right. tempNodePtr = nodePtr->right; // Go to the end left node while (tempNodePtr->left) tempNodePtr = tempNodePtr->left; // reattach the left subtree tempNodePtr->left = nodePtr->left; tempNodePtr = nodePtr; // reattach the right subtree nodePtr = nodePtr->right; delete tempNodePtr; } } void BinaryTree::remove(int number) { deleteNode(number, root); } void BinaryTree::balance() { if (root != nullptr) { vector vectorRecord; toVector(&vectorRecord); destroySubTree(root); balance(vectorRecord, 0, vectorRecord.size() - 1); } } void BinaryTree::balance(vector vectorRecord, int start, int stop) { int middle = (start + stop) / 2; if (start == stop) { insert(vectorRecord[middle]); } else if (start < stop) { insert(vectorRecord[middle]); balance(vectorRecord, start, middle - 1); balance(vectorRecord, middle + 1, stop); } } void BinaryTree::toVector(vector* vectorRecord) { toVector(vectorRecord, root); } void BinaryTree::toVector(vector* vectorRecord, TreeNode* subTree) { if (subTree != nullptr) { toVector(vectorRecord, subTree->left); vectorRecord->push_back(subTree->value); toVector(vectorRecord, subTree->right); } } // Need help on this function bool BinaryTree::isSameTree(BinaryTree* anotherTree) { return false; }``````
Well as you have .toVector(), one easy way would be to obtain the vector for the current tree, and the vector for the specified anotherTree and then compare these vectors (== is defined for vector).
How would I call on the toVector for anotherTree and currentTree?
Also, why is vectorRecord passed by pointer and not by ref?

 How would I call on the toVector for anotherTree and currentTree?

Not tried, but something like:

 ``123456789`` ``````bool BinaryTree::isSameTree(BinaryTree* anotherTree) { vector t1, t2; toVector(&t1); toVector(&t2, anotherTree->root); return t1 == t2; }``````

Last edited on
Okay, got it working. Thanks for your help.
Topic archived. No new replies allowed.