c$++$ Write two functions for our Binary Search Tree class that calculate the minimum and maximum value found in the tree.

#ifndef TREE$\_$H

#define TREE$\_$H

#include

#include

using namespace std;

template

struct node$\{$

TYPE value;

node$*$ left;

node$*$ right;

node$()\{$

left $=$ nullptr;

right $=$ nullptr;

$\}$

node$($TYPE value$)\{$

this$->$value $=$ value;

left $=$ nullptr;

right $=$ nullptr;

$\}$

$\}$;

template

class Tree $\{$

public:

node$*$ root;

Tree$()\{$

root $=$ nullptr;

$\}$

Tree$($node$*$ root$)\{$

this$->$root $=$ root;

$\}$

node$*$ search$($TYPE value, node$*$ current$)\{$

if$($current $==$ nullptr$)$

return nullptr;

else if$($value $==$ current$->$value$)$

return current;

else if$($value $<$ current$->$value$)$

return search$($value$,$ current$->$left$)$;

else if$($value $>$ current$->$value$)$

return search$($value$,$ current$->$right$)$;

$\}$

node$*$ search$($TYPE value$)\{$

return search$($value$,$ this$->$root$)$;

$\}$

void insert$($TYPE value, node$*$ current$)\{$

if$($this$->$root $==$ nullptr$)\{$

root $=$ new node$($value$)$;

$\}$

else if$($value $<$ current$->$value$)\{$

if$($current$->$left $==$ nullptr$)$

current$->$left $=$ new node$($value$)$;

else

insert$($value$,$ current$->$left$)$;

$\}$

else if$($value $>=$ current$->$value$)\{$

if$($current$->$right $==$ nullptr$)$

current$->$right $=$ new node$($value$)$;

else

insert$($value$,$ current$->$right$)$;

$\}$

$\}$

void insert$($TYPE value$)\{$

insert$($value$,$ this$->$root$)$;

$\}$

void display$($node$*$ current$)\{$

if$($current $!=$ nullptr$)\{$

display$($current$->$left$)$;

cout $<<$ current$->$value $<<"("<<$ current $<<")$

$"$;

display$($current$->$right$)$;

$\}$

$\}$

void display$()\{$

display$($this$->$root$)$;

$\}$

node$*$ successor$($node$*$ current$)\{$

current $=$ current$->$right;

while $($current && current$->$left $!=$ nullptr$)$

current $=$ current$->$left;

return current;

$\}$

node$*$ remove$($TYPE target, node$*$ current$)\{$

if $($current $==$ nullptr$)$

return current;

else if $($target $<$ current$->$value$)$

current$->$left $=$ remove$($target$,$ current$->$left$)$;

else if $($target $>$ current$->$value$)$

current$->$right $=$ remove$($target$,$ current$->$right$)$;

else $\{$

if $($current$->$left $==$ nullptr and current$->$right $==$ nullptr$)\{$

delete current;

return nullptr;

$\}$

else if $($current$->$left $==$ nullptr$)\{$

node$*$ temp $=$ current$->$right;

delete current;

return temp;

$\}$

else if $($current$->$right $==$ nullptr$)\{$

node$*$ temp $=$ current$->$left;

delete current;

return temp;

$\}$

node$*$ temp $=$ successor$($current$)$;

current$->$value $=$ temp$->$value;

current$->$right $=$ remove$($temp$->$value, current$->$right$)$;

$\}$

return current;

$\}$

node$*$ remove$($TYPE value$)\{$

return remove$($value$,$ this$->$root$)$;

$\}$

int size$($node$*$ current$)\{$

if$($current $==$ nullptr$)\{$

return $0$;

$\}$

else $\{$

return size$($current$->$left$)+$ size$($current$->$right$)+1$;

$\}$

$\}$

int size$()\{$

return size$($this$->$root$)$;

$\}$

void makeArray$($node$*$ current, vector$*>$ &list$)\{$

if$($current $!=$ nullptr$)\{$

this$->$makeArray$($current$->$left, list$)$;

list.push$\_$back$($current$)$;

this$->$makeArray$($current$->$right, list$)$;

$\}$

$\}$

node$*$ balanceTree$($vector$*>$ &list,

int begin, int end$)\{$

if$($begin $>$ end$)\{$

return nullptr;

$\}$

int mid $=($begin $+$ end$)/2$;

list$[$mid$]->$left $=$ balanceTree$($list$,$ begin, mid $-1)$;

list$[$mid$]->$right $=$ balanceTree$($list$,$ mid $+1,$ end$)$;

return list$[$mid$]$;

$\}$

void balance$()\{$

vector$*>$ list;

this$->$makeArray$($this$->$root, list$)$;

this$->$root $=$ this$->$balanceTree$($list$,0,$ list.size$()-1)$;

$\}$

int totalNodes$($node$*$ current$)//$ returns the size of the tree

$\{$

if $($current $==$ nullptr$)$

return $0$;

int l $=$ totalNodes$($current$->$left$)$;

int r $=$ totalNodes$($current$->$right$)$;

return $1+$ l $+$ r;

$\}$

int totalNodes$()\{$

return totalNodes$($this$->$root$)$;

$\}$

$\}$;

#endif