ANSWER ONLY WHERE IT SAYS $//$YOUR CODE HERE. USE C$++$ ONLY PLEASE!

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

void loadFile$($string fname, fstream& file$)$

$\{$

file.open$($fname$.$c$\_$str$())$;

if $($file$.$fail$())$

$\{$

cout $$ "Cannot open file $"$ fname $$ endl;

$\}$

$\}$

$/*$

# Purpose: Class definition of a simple implementation of an ordered map ADT,

# mapping integers keys to integer values, using a binary search tree $($BST$)$ with a

linked$-$structure representation

# NOTE: only basic methods of the ordered map ADT $($i$.$e$.,$ put, erase, find, size,

empty$),$ and some auxiliary functions $($e$.$g$.,$ successor and predecessor$)$ implemented

# NOTE: For the sake of consistency with the implementation on other programming

languages $($e$.$g$.,$ Java and C$++),$ this simple implementation does not use overloading

of the $[]$ or del operator in Python. Also, the documentation$/$comments$/$description

of methods uses the term "NULL" instead of "None" $($as actually used in Python

implementations$)$

$*/$

class BSTMap

$\{$

public:

$//$ simple data structure used to create nodes for $($linked$-$list$)$ BST$-$based

implementation of an ordered map ADT

$//$ from integer keys to integer values

class Node $\{$

public:

int key;

int value;

Node$*$ left;

Node$*$ right;

Node$*$ parent;

$//$ node constructors

Node$()$ : left$($NULL$),$ right$($NULL$),$ parent$($NULL$)\{\}$;

Node$($int k$,$ int v$)$ :

key$($k$),$ value$($v$),$ left$($NULL$),$ right$($NULL$),$ parent$($NULL$)\{\}$;

Node$($int k$,$ int v$,$ Node$*$ l$,$ Node$*$ r$,$ Node$*$ p$)$ : key$($k$),$ value$($v$),$ left$($l$),$

right$($r$),$ parent$($p$)\{\}$;

$//$ node desctructor

virtual ~Node$()\{\}$;

$//$ overloading output stream for a representation of BST node w

friend ostream& operatorostream& os$,$ const Node& w$)\{$

os $$ w$.$key :$"$ w$.$value ;

return os;

$\}$;

$//($overloadable$)$ print node stats

virtual void printStats$()\{$ cout this; $\}$;

$\}$;

$//$ prints a representation of BST node w

$//($overloadable$)$

$//$ INPUT: node w

virtual void printNode$($const Node$*$ w$)$ const $\{$ if $($w$)$ cout Node$*)$ w$)$; $\}$;

$//$ tree constructor

BSTMap$()$ : root$($NULL$),$ n$(0)\{\}$;

$//$ tree destructor

virtual ~BSTMap$()$;

$//$ basic map operations

Node$*$ find$($int k$)$ const;

void put$($int k$,$ int v$)$;

void erase$($int k$)$;

int size$()$ const;

bool empty$()$ const;

$//$ auxiliary utilities

Node$*$ youngestAncestorType$($Node$*$ w$,$ bool check$\_$left$)$ const;

Node$*$ youngestDescendantType$($Node$*$ w$,$ bool check$\_$left$)$ const;

Node$*$ successor$($Node$*$ w$)$ const;

Node$*$ predecessor$($Node$*$ w$)$ const;

$//$ print utilities

void print$()$ const; $//$ print as parenthetic string

void printTree$($Node$*$ s$,$ int space$)$ const;

void printMap$()$ const;

void printTreeMap$($Node$*$ s$,$ int space$)$ const;

protected:

$//$ data member: tree root node

Node$*$ root;

$//($overloadable$)$ auxiliary node creation utility

virtual Node$*$ createNode$($int k$,$ int v$,$ Node$*$ l$,$ Node$*$ r$,$ Node$*$ p$)\{$ return new

Node$($k$,$v$,$l$,$r$,$p$)$; $\}$;

$//$ auxiliary print utilities

void printAux$($const Node$*$ w$,$ bool simple$)$ const; $//$ print utility

void printTreeAux$($Node$*$ s$,$ int space, bool simple$)$ const;

$//$ auxiliary utilities

void makeChild$($Node$*$ p$,$ Node$*$ c$,$ bool isLeft$)$;

Node$*$ findNode$($int k$)$ const;

virtual Node$*$ putNode$($int k$,$ int v$)$;

virtual Node$*$ eraseNode$($int k$)$;

private:

$//$ auxiliary utilities

virtual void deleteNode$($Node$*$ w$)$;

virtual void deleteAll$()$;

Node$*$ removeNode$($Node$*$ w$)$;

$//$ data member: tree size $($number of nodes$/$map entries$)$

int n;

$\}$;

$/*$

$*$Purpose: Implement member functions$/$methods of BSTMap class

$*/$

$/*$

# utility$/$aux function to print out a parenthetic string representation of the

BST

# INPUT: a node w in the BST $($or subclass$)$ whose subtree is to be

# printed out; a boolean flag, simple, determining whether a

# simple key:value pair of the BST node or $($if overloaded$)$ a

# possibly more sophisticated representation based on

# characteristics of a subclass object

$*/$

void

BSTMap::printAux$($const BSTMap::Node$*$ w$,$ bool simple$)$ const $\{$

if $($w$)\{$

if $($simple$)$

cout w ;

else $\{$

cout ;

printNode$($w$)$;

cout ;

$\}$

cout ;

printAux$($w$->$left, simple$)$;

cout ;

printAux$($w$->$right, simple$)$;

cout ;

$\}$

$\}$

$//$ print out a parenthetic string representation of the whole BST

void

BSTMap::print$()$ const $\{$

printAux$($root$,$ false$)$;

cout $$ endl;

$\}$

$//$ print out a parenthetic string representation of the whole BST

$//$ using simply the key$-$value info of the map entries in each node

void

BSTMap::printMap$()$ const $\{$

printAux$($root$,$ true$)$;

cout $$ endl;

$\}$

$/*$

# utility$/$aux method to print out a tree$-$like layout of the whole

# BST using a reverse inorder traversal INPUT: a node s in the BST

# whose rooted subtree needs to be printed; a natural number,

# space, for the minimum space separation required between the

# root and left side of the terminal and between each node and its

# children; a boolean flag, simple, determining whether a simple

# key:value pair of We expect you to com