Add a new method, getMaxValue, to the BinarySearchTree class discussed in class and defined here that takes no parameters and returns the maximum value (not key) stored in the tree. If the tree is empty, throw a standard length error exception saying so. Implement this function using recursion.
Match the provided code fragments to the placeholder within the existing code to create this new function using proper syntax and logic. If there is more than one way to create this function with the fragments provided, select the best option.
template
class BinarySearchTree {
public:
BinarySearchTree () = default;
BinarySearchTree ( const BinarySearchTree & original );
BinarySearchTree & operator= ( BinarySearchTree rhs );
~BinarySearchTree ();
Value search ( const Key & key ) const;
void insert ( const Key & key, const Value & value );
void remove ( const Key & key );
void printInorder() const;
int getHeight () const;
void clear ();
/********************************************************************
** Add public function declaration (prototype) here
********************************************************************/
____1____ getMaxValue( ____2____ );
private:
struct Node;
Node * root_ = nullptr;
void clear ( Node * node );
void insertIterative( Node * node );
void insertRecursive( Node * parent, Node * nodeToInsert );
void remove ( Node * node );
void printInorder ( Node * node ) const;
int getHeight ( Node * node ) const;
Node * makeCopy ( Node * node );
Node * searchIterative( const Key & key ) const;
Node * searchRecursive( Node * node, const Key & key ) const;
bool replaceChild( Node * parent,
Node * currentChild,
Node * newChild );
/********************************************************************
** Add private function declaration (prototype) here
********************************************************************/
____3____ getMaxValue( ____4____ );
};
template
struct BinarySearchTree::Node
{
friend std::ostream & operator<<( std::ostream & stream, const Node & node )
{
stream << "Key: \"" << node.key_ << "\", Value: \"" << node.value_ << "\"\n";
return stream;
}
Node( const Key & key = Key(), const Value & value = Value() ); // Also serves as the default constructor
Key key_;
Value value_;
Node * left_ = nullptr;
Node * right_ = nullptr;
Node * parent_ = nullptr;
};
BinarySearchTree.hxx:
/********************************************************************
** Add function definitions here
********************************************************************/
template
____5____ BinarySearchTree::getMaxValue( ____6____ )
{
if( root_ == nullptr ) throw std::length_error( "Max value of empty tree not possible" );
return getMaxValue( ____7____ );
}
template
____8____ BinarySearchTree::getMaxValue( ____9____ )
{
___10____ max = ___11____;
if( ___12____ ___13____ )
{
___14____ maxLeft = getMaxValue( ___15____ );
max = maxLeft > max ? maxLeft : max;
}
if( ___16____ ___17____ )
{
___18____ maxRight = getMaxValue( ___19____ );
max = maxRight > max ? maxRight : max;
}
return max;
}