Answer Happy

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,
These two trees, even though they have different structures, are
equivalent, and should return a true.
If we compare these two trees:
They will return a false when sent to the function.
For the Trees, implement the following:
BINARYTREE.h
#ifndef BINARY_TREE_INTERFACE_
#define BINARY_TREE_INTERFACE_
#include "NotFoundException.h"
template<class ItemType>
class BinaryTreeInterface
{
public:
virtual bool isEmpty() const = 0;
virtual int getHeight() const = 0;
virtual int getNumberOfNodes() const = 0;
virtual ItemType getRootData() const = 0;
virtual void setRootData(const ItemType& newData) = 0;
virtual bool add(const ItemType& newData) = 0;

virtual bool remove(const ItemType& data) = 0;

virtual void clear() = 0;
virtual ItemType getEntry(const ItemType& anEntry) const
throw(NotFoundException) = 0;
virtual bool contains(const ItemType& anEntry) const = 0;
virtual void preorderTraverse(void visit(ItemType&)) const =
0;
virtual void inorderTraverse(void visit(ItemType&)) const =
0;
virtual void postorderTraverse(void visit(ItemType&)) const =
0;
virtual ~BinaryTreeInterface() { }
};
#endif
BINARYNODE.h
#ifndef BINARY_NODE_
#define BINARY_NODE_
#include <memory>
template<class ItemType>
class BinaryNode
{
private:
ItemType item; // Data portion
std::shared_ptr<BinaryNode<ItemType>> leftChildPtr; //
Pointer to left child
std::shared_ptr<BinaryNode<ItemType>> rightChildPtr; //
Pointer to right child
public:
BinaryNode();
BinaryNode(const ItemType& anItem);
BinaryNode(const ItemType& anItem,
std::shared_ptr<BinaryNode<ItemType>> leftPtr,
std::shared_ptr<BinaryNode<ItemType>> rightPtr);
void setItem(const ItemType& anItem);
ItemType getItem() const;
bool isLeaf() const;
auto getLeftChildPtr() const;
auto getRightChildPtr() const;
void
setLeftChildPtr(std::shared_ptr<BinaryNode<ItemType>>
leftPtr);
void
setRightChildPtr(std::shared_ptr<BinaryNode<ItemType>>
rightPtr);
};
#endif
BINARYNODETREE.h
#ifndef BINARY_NODE_TREE_
#define BINARY_NODE_TREE_
#include <memory>
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
#include "PrecondViolatedExcep.h"
#include "NotFoundException.h"
template<class ItemType>
class BinaryNodeTree : public
BinaryTreeInterface<ItemType>
{
private:
std::shared_ptr<BinaryNode<ItemType>> rootPtr;
protected:
int
getHeightHelper(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr) const;
int
getNumberOfNodesHelper(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr) const;
auto balancedAdd(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr,
std::shared_ptr<BinaryNode<ItemType>>
newNodePtr);
std::shared_ptr<BinaryNode<ItemType>>
moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr);
virtual std::shared_ptr<BinaryNode<ItemType>>
removeValue(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr,
const ItemType target, bool& success);
auto findNode(std::shared_ptr<BinaryNode<ItemType>>
treePtr,
const ItemType& target,
bool& success) const;
std::shared_ptr<BinaryNode<ItemType>> copyTree(const
std::shared_ptr<BinaryNode<ItemType>> oldTreeRootPtr)
const;
void destroyTree(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr);
void preorder(void visit(ItemType&),
std::shared_ptr<BinaryNode<ItemType>> treePtr)
const;
void inorder(void visit(ItemType&),
std::shared_ptr<BinaryNode<ItemType>> treePtr)
const;
void postorder(void visit(ItemType&),
std::shared_ptr<BinaryNode<ItemType>> treePtr)
const;
public:
BinaryNodeTree();
BinaryNodeTree(const ItemType& rootItem);
BinaryNodeTree(const ItemType& rootItem,
const std::shared_ptr<BinaryNodeTree<ItemType>>
leftTreePtr,
const std::shared_ptr<BinaryNodeTree<ItemType>>
rightTreePtr);
BinaryNodeTree(const BinaryNodeTree<ItemType>&
tree);
virtual ~BinaryNodeTree();
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const throw(PrecondViolatedExcep);
void setRootData(const ItemType& newData);
bool add(const ItemType& newData); // Adds a node
bool remove(const ItemType& data); // Removes a node
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);
};
#endif

NOTFOUNDEXCEPTION.h
PrecondViolatedExcept.h
#include <stdexcept>
#include <string>
class PrecondViolatedExcep : public std::logic_error
{
public:
PrecondViolatedExcep(const std::string& message =
"");
};
#endif
BinarySearchTree.h
#ifndef BINARY_SEARCH_TREE_
#define BINARY_SEARCH_TREE_
#include <memory>
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
#include "BinaryNodeTree.h"
#include "NotFoundException.h"
#include "PrecondViolatedExcep.h"
template<class ItemType>
class BinarySearchTree : public
BinaryNodeTree<ItemType>
{
private:
std::shared_ptr<BinaryNode<ItemType>> rootPtr;
protected:
auto placeNode(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr,
std::shared_ptr<BinaryNode<ItemType>> newNode);
std::shared_ptr<BinaryNode<ItemType>>
removeValue(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr,
const ItemType target,
bool& success) override;
auto removeNode(std::shared_ptr<BinaryNode<ItemType>>
nodePtr);
auto
removeLeftmostNode(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr,
ItemType& inorderSuccessor);
auto findNode(std::shared_ptr<BinaryNode<ItemType>>
treePtr,
const ItemType& target) const;
public:
BinarySearchTree();
BinarySearchTree(const ItemType& rootItem);
BinarySearchTree(const BinarySearchTree<ItemType>&
tree);
virtual ~BinarySearchTree();
bool isEmpty() const override;
int getHeight() const override;
int getNumberOfNodes() const override;
ItemType getRootData() const
throw(PrecondViolatedExcep)override;
void setRootData(const ItemType& newData) const
throw(PrecondViolatedExcep);
bool add(const ItemType& newEntry) override;
bool remove(const ItemType& anEntry) override;
void clear() override;
ItemType getEntry(const ItemType& anEntry) const
throw(NotFoundException)override;
bool contains(const ItemType& anEntry) const override;
void preorderTraverse(void visit(ItemType&)) const
override;
void inorderTraverse(void visit(ItemType&)) const
override;
void postorderTraverse(void visit(ItemType&)) const
override;
BinarySearchTree<ItemType>& operator=(const
BinarySearchTree<ItemType>& rightHandSide);
};
#endif