#pragma once

#include"BinaryTreeNode.h$"$

using namespace std;

template

class BSTree : public BinaryTree $\{$

protected:

BinaryTreeNode$*$ root; $//$ root of tree

public:

BSTree$()$ : root$($NULL$)\{\}$;

BSTree$($const BSTree&$)$;

BSTree$($T data$)\{$ root $=$ new BinaryTreeNode$($data$)$; $\}$;

virtual ~BSTree$()\{$ if $($root$)$ delete root; $\}$;

BinaryTreeNode$*$ getRoot$()\{$

return root;

$\}$

T findSmallest$($BinaryTreeNode$*$ nodep$)$;

virtual bool insert$($BinaryTreeNode$*$ nodep, const T& x$)$;

virtual const T$*$ const search$($BinaryTreeNode$*$ nodep, const T& x$)$;

virtual bool remove$($BinaryTreeNode$*$ nodep, const T& x$)$;

$\}$;

template

T BSTree::findSmallest$($BinaryTreeNode$*$ nodep$)\{$

if $($nodep$->$GetLeftChild$()!=$ nullptr$)\{$

return findSmallest$($nodep$->$GetLeftChild$())$;

$\}$

$//$ This is the data contained within the smallest node

return nodep$->$GetData$()$;

$\}$

template

const T$*$ const BSTree::search$($BinaryTreeNode$*$ nodep, const T& x$)\{$

if $($nodep $==0)\{$

return NULL;

$\}$

if $($x $==$ nodep$->$GetData$())\{$

return &$($nodep$->$GetData$())$;

$\}$

if $($x $$ nodep$->$GetData$())\{$

return search$($nodep$->$GetLeftChild$(),$ x$)$;

$\}$

else $\{$

return search$($nodep$->$GetRightChild$(),$ x$)$;

$\}$

$\}$

template

bool BSTree::insert$($BinaryTreeNode$*$ nodep, const T& x$)\{$

$//$To Do: Write your code here

$\}$

template

bool BSTree::remove$($BinaryTreeNode$*$ nodep, const T& x$)\{$

$//$To Do: Write your code here

$\}$You need to complete a BSTree $($Binary Search Tree$)$ class in the BSTree.h file. In

particular, this class inherits from the BinaryTree class. Thus, the parent functions

such as

PreOrderTraverse$($BinaryTreeNode