Question

Consider the class specifications for the Binary Tree class and BinarySearch Tree class below: // Binary Tree.h #include <iostream> using namespace std; //Definition of the Node template <class elemType struct TreeNode { elemType data; TreeNode<elemType> *left; TreeNode<elemType *right; }; //Definition of class Binary Tree template <class elemType> class Binary Tree { protected: TreeNode<elemType> *root; public: BinaryTree(); BinaryTreel const BinaryTree<elemType>& otherTree); -Binary Tree(): bool is Empty() const; virtual bool search(const elemTypes searchItem) const = 0; virtual void insert(const elemTypek insertItem) = 0; virtual void deleteNode(const elemType deleteItem) = 0; private int height (TreeNode<elemType *p) const; int nodeCount(TreeNode<elem Type> *p) const; int leafCount(TreeNode<elenType> *p) const; // BinarySearchTree.h #include "Binary Tree.h" using namespace std; template <class elenType class Binary Search Tree: public Binary TreecelemType> { public: bool search(const elemType searchItem) const; void insert(const eleTypek insertItem); void deleteNode(const elemType deleteItem); private void displayAscending(TreeNodecelenType sp) const; TreeNodecelenType> * getTree lax(TreeNodeelemTypes #p) const; TreeNodecelentype * getTreelin(TreeNode<elemType> *D) const; ); Write a member function for the BinarySearch Tree class that returns a pointer to the node with the smallest value

Answer 1

// BinaryTree.h
#include <iostream>
using namespace std;

// Definition of the Node
template <class elemType>
struct TreeNode
{
   elemType data;
   TreeNode<elemType> *left;
   TreeNode<elemType> *right;
};

// Definition of Binary Tree  
template <class elemType>
class BinaryTree
{
protected:
   TreeNode<elemType> *root;
  
public:
   BinaryTree();
   BinaryTree(const BinaryTree<elemType> &otherTree);
   ~BinaryTree();
   bool isEmpty() const;
   virtual bool search(const elemType& searchItem) const = 0;
   virtual void insert(const elemType& insertItem) = 0;
   virtual void deleteNode(const elemType& deleteItem) = 0;

private:
   int height(TreeNode<elemType> *p) const;
   int nodeCount(TreeNode<elemType> *p) const;  
   int leafCount(TreeNode<elemType> *p) const;
};

//end of BinaryTree.h

// BinarySearchTree.h
#include "BinaryTree.h"
using namespace std;

template <class elemType>
class BinarySearchTree : public BinaryTree<elemType>
{
public:
   bool search(const elemType& searchItem) const;
   void insert(const elemType& insertItem);
   void deleteNode(const elemType& deleteItem);
   TreeNode<elemType> * getTreeMin() const; // member function that returns a pointer to the node with the smallest value
private:
   void displayAscending(TreeNode<elemType> *p) const;
   TreeNode<elemType> * getTreeMax(TreeNode<elemType> *p) const;
   TreeNode<elemType> * getTreeMin(TreeNode<elemType> *p) const;
  
};

// function to return the pointer to the node with the smallest value in the tree
template <class elemType>
TreeNode<elemType>* BinarySearchTree<elemType>:: getTreeMin() const
{
   // can directly access root as it is protected member of the base class
   return getTreeMin(root); // call the helper function getTreeMin with root as the parameter
}

// helper function to return the pointer to the node with smallest value starting from node p
// Since it is a BinarySearchTree, hence the smallest value is the leftmost node of the tree
template <class elemType>
TreeNode<elemType>* BinarySearchTree<elemType>::getTreeMin(TreeNode<elemType> *p) const
{
   // if p is null, return null
   if(p == NULL)
       return NULL;
   else if(p->left == NULL) // if p is the left most node of the tree return p
       return p;
   else
       return getTreeMin(p->left); // call getTreeMin with left node of p
}

//end of BinarySearchTree.h