#ifndef BINARYSEARCHTREE$\_$H

#define BINARYSEARCHTREE$\_$H

#include

#include

#include

#include

#include"bstnode.h$"$

$//$ Node implementation: Implemented

template

class Node $\{$

public:

Node$($Type v$,$ Node$*$ l$,$ Node$*$ r$)$ :val$($v$),$ l$($l$),$ r$($r$)\{\}$

Node$()$ :Node$(0,$ nullptr, nullptr$)\{\}$

Node$*$ left$()\{$ return l; $\}$

Node$*$ right$()\{$ return r; $\}$

void left$($Node $*$ lft$)\{$ l $=$ lft; $\}$

void right$($Node $*$ rht$)\{$r $=$ rht;$\}$

Type value$()\{$ return val; $\}$

void value$($Type v$)\{$ val $=$ v; $\}$

private:

Type val;

Node $*$l$,*$r;

$\}$;

template

class BinarySearchTree $\{$

public:

$//$ Public Interface Functions: All of these are implemented

BinarySearchTree$()$;

~BinarySearchTree$()$;

void printInorder$()$;

void printPostorder$()$;

void printPreorder$()$;

void insert$($Type value$)$;

void remove$($Type value$)$;

Type min$()$ const;

Type max$()$ const;

int height$()$ const;

bool search$($Type value$)$ const;

bool empty$()$ const;

void printTree$()$ const;

void report$()$ const;

private:

$//$ Member variable root

Node$*$ root;

$//$Auxillary recursive bst functions

$//$public interface functions call these

$//$You will implement these functions.

$//$ Tree traversal, second parameter is a "function" with

$//$ return type void and parameter Node$*,$ i$.$e:

$//$ void process$($Node$*)$

void inorder$($Node$*$ node, std::function$*)>$ proc$)$;

void preorder$($Node$*$ node, std::function$*)>$ proc$)$;

void postorder$($Node$*$ node, std::function$*)>$ proc$)$;

Node$*$ min$($Node $*$node$)$ const;

Node$*$ max$($Node $*$node$)$ const;

int height$($Node$*$ node$)$ const;

Node$*$ insert$($Node $*$node$,$ Type value$)$;

bool search$($Node $*$node$,$ Type value$)$ const;

Node$*$ remove$($Node $*$node$,$ Type value$)$;

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

$\}$;

$//----------------------------------------------------------$

$//--------------$ Binary Search Tree Function Implementations

$//$

$//$ Public Interface functions

$//$ Completley Implemented, nothing to do$.$ These functions

$//$ call the recursive helper functions you will implement

$//$ below.

$//$ Constructor

template

BinarySearchTree::BinarySearchTree$()$ :root$($nullptr$)\{\}$

$//$ Destructor

template

BinarySearchTree::~BinarySearchTree$()\{$

$//$Use the post order traversal to delete the nodes.

$//$lambda function to delete a node n:

$//[]($Node$*$ n$)\{$delete n; $\}$

postorder$($root$,[]($Node$*$ n$)\{$delete n; $\})$;

$\}$

template

void BinarySearchTree::printInorder$()\{$

$//$Use inorder traversal to print items in a node in the tree.

$//$lambda function to print the value in a node:

$//$lambda to print$->"[]($Node$*$ n$)\{$std::cout $<<$ n$->$value$()<<$ std::endl; $\}"$

inorder$($root$,[]($Node$*$ n$)\{$std::cout $<<$ n$->$value$()<<""$; $\})$;

std::cout $<<$ std::endl;

$\}$

template

void BinarySearchTree::printPreorder$()\{$

$//$Use pre order traversal to print items in a node in the tree.

$//$lambda function to print the value in a node:

$//$lambda to print$->"[]($Node$*$ n$)\{$std::cout $<<$ n$->$value$()<<$ std::endl; $\}"$

preorder$($root$,[]($Node$*$ n$)\{$std::cout $<<$ n$->$value$()<<""$; $\})$;

std::cout $<<$ std::endl;

$\}$

template

void BinarySearchTree::printPostorder$()\{$

$//$Use post order traversal to print items in a node in the tree.

$//$lambda function to print the value in a node:

$//$lambda to print$->"[]($Node$*$ n$)\{$std::cout $<<$ n$->$value$()<<$ std::endl; $\}"$

postorder$($root$,[]($Node$*$ n$)\{$std::cout $<<$ n$->$value$()<<""$; $\})$;

std::cout $<<$ std::endl;

$\}$

template

void BinarySearchTree::insert$($Type value$)\{$

root $=$ insert$($root$,$ value$)$;

$\}$

template

void BinarySearchTree::remove$($Type value$)\{$

root $=$ remove$($root$,$ value$)$;

$\}$

template

Type BinarySearchTree::min$()$ const $\{$

assert$($root $!=$ nullptr$)$;

Node$*$ node $=$ min$($root$)$;

return node$->$value$()$;

$\}$

template

Type BinarySearchTree::max$()$ const $\{$

assert$($root $!=$ nullptr$)$;

Node$*$ node $=$ max$($root$)$;

return node$->$value$()$;

$\}$

template

int BinarySearchTree::height$()$ const $\{$

return height$($root$)$;

$\}$

template

bool BinarySearchTree::search$($Type value$)$ const $\{$

return search$($root$,$ value$)$;

$\}$

template

bool BinarySearchTree::empty$()$ const $\{$

return $($root $==$ nullptr$)$;

$\}$

template

void BinarySearchTree::printTree$()$ const $\{$

printTree$($root$,0)$;

$\}$

$//----------------------------------------------------------$

$//$

$//$ Private Recursive Functions: You Implement These.

$//$

$//$ Inorder Traversal: Implemented so you can see how passing a function into

$//$ another function works, other traversals remain for you to implement. the second

$//$ p