C$++$ Visual Studio. Same Tree Function. Create a function called bool isSameTree$($Tree $*)$; that will take an argument of a tree. It will return a true if the argument is the equivalent tree.

So for example, if we have two trees,

insert$($abc$)$;

insert$($def$)$;

insert$($ghi$)$;

insert$($def$)$;

insert$($abc$)$;

insert$($ghi$)$;

These two trees, even though they have different structures, are equivalent, and should return true.

If we compare these two trees:

insert$($abc$)$;

insert$($ghi$)$;

insert$($abc$)$;

insert$($def$)$;

insert$($ghi$)$;

They will return a false when sent to the function.

The program already has the files: BinaryTreeInterface.h$,$ BinaryNode.h$,$ BinaryNode.cpp$,$ BinaryNodeTree.h$,$ BinaryNodeTree.cpp$,$ NotFoundException.h$,$ PrecondViolatedExcept.h$,$ BinarySearchTree.h$,$ and BinarySearchTree.cpp$.$ In other words I need to implement the Same Tree Function in the driver, or source file. I would appreciate a practical example using the below methods as the basis and I would greatly appreciate comments. Please include $4$ trees in total. $2$ that are equivalent and return true and two that are not equivalent and return false. BinaryNodeTree has getRootData$()$ and BinaryNode has GetLeftChildPtr$()/$GetRightChildPtr$().$ It must use a string in the isSameTree function as it must be the same three letter combinations above.

BinaryNode Methods:

BinaryNode$()$;

BinaryNode$($const ItemType& anItem$)$;

BinaryNode$($const ItemType& anItem, std::shared$\_$ptr$>$ leftPtr, std::shared$\_$ptr$>$ rightPtr$)$;

void setItem$($const ItemType& anItem$)$;

ItemType getItem$()$ const;

bool isLeaf$()$ const;

auto getLeftChildPtr$()$ const;

auto getRightChildPtr$()$ const;

void setLeftChildPtr$($std::shared$\_$ptr$>$ leftPtr$)$;

void setrightChildPtr$($std::shared$\_$ptr$>$ rightPtr$)$;

BinaryNodeTree Methods:

protected:

int getHeightHelper$($std::shared$\_$ptr$>$ subTreePtr$)$ const;

int getNumberOfNodesHelper$($std::shared$\_$ptr$>$ subTreePtr$)$ const;

auto balancedAdd$($std::shared$\_$ptr$>$ subTreePtr, std::shared$\_$ptr$>$ newNodePtr$)$;

virtual auto removeValue$($std::shared$\_$ptr$>$ subTreePtr, const ItemType target, bool& isSuccessful$)$;

auto moveValuesUpTree$($std::shared$\_$ptr$>$ subTreePtr$)$;

virtual auto findNode$($std::shared$\_$ptr$>$ subTreePtr, const ItemType& target, bool& isSuccessful$)$ const;

auto copyTree$($const std::shared$\_$ptr$>$ oldTreeRootPtr$)$ const;

void destroyTree$($std::shared$\_$ptr$>$ subTreePtr$)$;

void preorder$($void visit$($ItemType&$),$ std::shared$\_$ptr$>$ treePtr$)$ const;

void inorder$($void visit$($ItemType&$),$ std::shared$\_$ptr$>$ treePtr$)$ const;

void postorder$($void visit$($ItemType&$),$ std::shared$\_$ptr$>$ treePtr$)$ const;

public:

BinaryNodeTree$()$;

BinaryNodeTree$($const ItemType& rootItem, const std::shared$\_$ptr$>$ leftTreePtr, const std::shared$\_$ptr$>$ rightTreePtr$)$;

BinaryNodeTree$($const std::shared$\_$ptr$>$& tree$)$;

virtual ~BinaryNodeTree$()$;

bool isEmpty$()$ const;

int getHeight$()$ const;

int getNumberOfNodes$()$ const;

ItemType getRootData$()$ const throw$($PrecondViolatedExcept$)$;

void setRootData$($const ItemType& newData$)$;

bool add$($const ItemType& newData$)$;

bool remove$($const ItemType& data$)$;

void clear$()$;

ItemType getEntry$($const ItemType& anEntry$)$ const throw$($notFoundException$)$;

bool contains$($const ItemType& anEntry$)$ const;

void preorderTraverse$($void visit$($ItemType&$))$ const;

void inorderTraverse$($void visit$($ItemType&$))$ const;

void postorderTraverse$($void visit$($ItemType&$))$ const;

BinaryNodeTree& operator$=($const BinaryNodeTree& rightHandSide$)$;

BinarySearchTree methods:

protected:

auto placeNode$($std::shared$\_$ptr$>$ subTreePtr, std::shared$\_$ptr$>$ newNode$)$;

auto removeValue$($std::shared$\_$ptr$>$ subTreePtr, const ItemType target, bool& isSuccessful$)$ override;

auto removeNode$($std::shared$\_$ptr$>$ nodePtr$)$;

auto removeLeftMostNode$($std::shared$\_$ptr$>$subTreePtr, ItemType& inorderSuccessor$)$;

auto findNode$($std::shared$\_$ptr$>$ treePtr, const ItemType& target$)$;

public:

BinarySearchTree$()$;

BinarySearchTree$($const ItemType& rootItem$)$;

BinarySearchTree$($const BinarySearchTree& tree$)$;

virtual ~BinarySearchTree$()$;

bool isEmpty$()$;

int getHeight$()$ const;

int getNumberOfNodes$()$ const;

ItemType getRootData$()$ const throw$($PrecondViolatedExcept$)$;

void setRootData$($const ItemType& newData$)$;

bool add$($const ItemType& newEntry$)$;

bool remove$($const ItemType& target$)$;

void clear$()$;

ItemType getEntry$($const ItemType& anEntry$)$ const throw$($notFoundException$)$;

bool contains$($const ItemType& anEntry$)$ const;

void preorderTraverse$($void visit$($ItemType&$))$ const;

void inorderTraverse$($void visit$($ItemType&$))$ const;

void p