Can someone please assist me with the program question below. it has to do with Binary search trees and finding a maxkey();

any help will be appreciated. below i attached the CPP file

#pragma once

#include

using namespace std;

template

struct Node

{

Node() : parent_(0), left_(0), right_(0) { }

V operator*() { return(value_); }

bool IsRoot() const { return(parent_ == NULL); }

bool IsExternal() const { return((left_ == NULL) && (right_ == NULL)); }

void Show(ostream& stream);

K key_;

Node* left_;

Node* parent_;

Node* right_;

V value_;

};

template

class BinarySearchTree

{

public:

class Iterator

{

public:

Iterator() { }

Iterator MaxKey();

Iterator(Node* node) : node_(node) { }

const Node& operator*() const { return(*node_); };

Node& operator*() { return(*node_); };

bool operator==(const Iterator& p) const

{ return(node_ == p.node_); }

bool operator!=(const Iterator& p) const

{ return(node_ != p.node_); }

Iterator& operator++();

private:

Node* node_;

friend class BinarySearchTree;

};

BinarySearchTree();

Iterator Find(const K& key);

Iterator Insert(const K& key, const V& value);

bool Erase(const K& key);

void Erase(const Iterator& i);

void Show(ostream& stream);

int Size() const;

bool Empty() const;

Iterator Begin();

Iterator End();

private:

Node* Eraser(Node* node);

void ExpandExternal(Node* node);

Node* RemoveAboveExternal(Node* node);

Node* Finder(const K& key, Node* node);

Node* Inserter(const K& key, const V& value);

Node* root_;

int size_;

Node* superRoot_;

};

template

BinarySearchTree::BinarySearchTree()

{

size_ = 0;

// Create the super root and make its left child the logical root of the tree.

superRoot_ = new Node;

ExpandExternal(superRoot_);

root_ = superRoot_->left_;

}

template

typename BinarySearchTree::Iterator BinarySearchTree::Find(const K& key)

{

Node* node = Finder(key, root_);

if (!node->IsExternal()) {

return(Iterator(node));

}

else { // not found, return end iterator

return(End());

}

}

template

Node* BinarySearchTree::Finder(const K& key, Node* node)

{

if (node->IsExternal()) {

return(node);

}

if (key == node->key_) {

return(node);

}

else if (key key_) {

return(Finder(key, node->left_));

}

else {

return(Finder(key, node->right_));

}

}

template

void BinarySearchTree::Show(ostream& stream)

{

root_->Show(stream);

return;

}

template

void Node::Show(ostream& stream)

{

if (!IsExternal()) {

left_->Show(stream);

stream

right_->Show(stream);

}

return;

}

template

typename BinarySearchTree::Iterator

BinarySearchTree::Insert(const K& key, const V& value)

{

Node* node = Inserter(key, value);

return(Iterator(node));

}

template

Node* BinarySearchTree::Inserter(const K& key, const V& value)

{

Node* node = Finder(key,root_);

while (!node->IsExternal()) {

node = Finder(key, node->right_);

}

ExpandExternal(node);

node->key_ = key;

node->value_ = value;

++size_;

return(node);

}

template

bool BinarySearchTree::Erase(const K& key)

{

Node* node = Finder(key, root_);

if (!node->IsExternal()) {

Eraser(node);

return(true);

}

else {

return(false);

}

}

template

void BinarySearchTree::Erase(const Iterator& i)

{

Eraser(i.node_);

}

template

Node* BinarySearchTree::Eraser(Node* node)

{

Node* remove;

// Is the node's left child an external node?

if (node->left_->IsExternal()) {

remove = node->left_;

}

else if (node->right_->IsExternal()) {

remove = node->right_;

}

else {

// Both children are internal nodes. Find the node's logical successor by

// going down to the right child subtree and then all the way down to the

// bottom left corner of that subtree.

remove = node->right_;

do {

remove = remove->left_;

} while (!remove->IsExternal());

Node* removeParent = remove->parent_;

node->key_ = removeParent->key_;

node->value_ = removeParent->value_;

}

--size_;

return(RemoveAboveExternal(remove));

}

template

void BinarySearchTree::ExpandExternal(Node* node)

{

node->left_ = new Node;

node->left_->parent_ = node;

node->right_ = new Node;

node->right_->parent_ = node;

size_ += 2;

}

template

Node* BinarySearchTree::RemoveAboveExternal(Node* node)

{

Node* child = node;

Node* parent = child->parent_;

Node* sibling = (child == parent->left_ ? parent->right_ : parent->left_);

if (parent == root_) {

root_ = sibling;

sibling->parent_ = NULL;

}

else {

Node* grandParent = parent->parent_;

if (parent == grandParent->left_) {

grandParent->left_ = sibling;

}

else {

grandParent->right_ = sibling;

}

sibling->parent_ = grandParent;

}

delete child;

delete parent;

size_ -= 2;

return(sibling);

}

template

int BinarySearchTree::Size() const

{

return(size_);

}

template

bool BinarySearchTree::Empty() const

{

return(size_ == 0);

}

template

typename BinarySearchTree::Iterator BinarySearchTree::Begin()

{

Node* node = root_;

// Travel down the left side of the tree to the lower-left external node.

while (!node->IsExternal()) {

node = node->left_;

}

// Return an iterator to the lower-leftmost internal node.

return(Iterator(node->parent_));

}

template

typename BinarySearchTree::Iterator BinarySearchTree::End()

{

return(Iterator(superRoot_));

}

template

typename BinarySearchTree::Iterator& BinarySearchTree::Iterator::operator++()

{

// Is there a right subtree?

Node* next = node_->right_;

if (!next->IsExternal()) {

// Yes, go down to its lowest node.

do {

node_ = next;

next = next->left_;

} while (!next->IsExternal());

}

else {

// No, go up until we see the parent of a left subtree.

next = node_->parent_;

while (node_ == next->right_) {

node_ = next;

next = next->parent_;

}

node_ = next;

}

return(*this);

}

Add a public member function to class BinarySearchTree that returns an iterator to the node with the largest key. Do not change the contents of the search tree. Your function should have the declaration: Hint, Iterator MaxKey ): Study the two functions Iterator Find (const K& key) and its helper function Node* Finder (const K& key, Node*node) . Most code to calculate something based on the tree contents (and not change the tree) will have code very similar to Find ().Such code is recursive - Find () calls the recursive helper function Finder ) with the root as a parameter. Find also "hides" the pointer to the returned node inside an Iterator object