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:

Iterator MaxKey();

Hint:

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.

#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(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 < node->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 << key_ << " " << value_ << endl;
	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);
	}