List the values of the Binary Search Tree pictured below in the order in

which $$in$-$order traversal$$ of the tree will visit them. Remember that this will also be

the sequence by which function BinarySearchTree::printElements$()($see BinarySearchTreeLab$9.$h$)$ prints out the values.

Show you listings.

$($We were told that no programming was needed, but here is BinarySearchTreeLab$9.$h anyway.$)$

#ifndef BINARY$\_$SEARCH$\_$TREE$\_$H

#define BINARY$\_$SEARCH$\_$TREE$\_$H

#include

#include "Vector.h$"$

using namespace std;

template

class BinarySearchTree

$\{$

private:

struct BinaryNode

$\{$

T element;

BinaryNode$*$ left;

BinaryNode$*$ right;

BinaryNode$($const T& theElement, BinaryNode$*$ lt$,$ BinaryNode$*$ rt$)$

: element$($theElement$),$ left$($lt$),$ right$($rt$)$

$\{\}$

BinaryNode$($const T&& theElement, BinaryNode$*$ lt$,$ BinaryNode$*$ rt$)$

: element$($std::move$($theElement$)),$ left$($lt$),$ right$($rt$)$

$\{\}$

$\}$;

public:

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

~BinarySearchTree$()$

$\{$

makeEmpty$()$;

$\}$

bool isEmpty$()$ const

$\{$

return root $==0$;

$\}$

void insert$($const T& x$)$

$\{$

$//$ calls private insert $...$

insert$($x$,$ root$)$; $//==>$ LAB $9$: add private fct from Module $6\mathrm{.}2$

$\}$

$//$ LAB $9$: print all elements $($values$)$ in line

void printElements$()$ const

$\{$

if $($isEmpty$())$

cout $$ "Empty tree" $$ endl;

else

printElements$($root$)$; $//=>$ LAB $9$: define private fct below

$\}$

$//$ LAB $9$: returns number of elements in BST

int size$()$ const

$\{$

return size$($root$)$; $//$ LAB $9$: define private fct below

$\}$

void printInternal$()$ const

$\{$

if $($isEmpty$())$

cout $$ "Empty tree" $$ endl;

else

printInternal$($root$,0)$;

$\}$

$//$ for destructor to call...

void makeEmpty$()$

$\{$

makeEmpty$($root$)$;

$\}$

private:

BinaryNode$*$ root;

$//$the private member fcts that do all the work...

void insert$($const T& x$,$ BinaryNode$*$& t$)$

$\{$

$//$ LAB $9$: COMPLETE

$\}$

void makeEmpty$($BinaryNode$*$& t$)$

$\{$

if $($t $!=0)$

$\{$

makeEmpty$($t$->$left$)$;

makeEmpty$($t$->$right$)$;

delete t;

$\}$

t $=0$;

$\}$

void printInternal$($BinaryNode$*$ t$,$ int offset$)$ const

$\{$

for $($int i $=1$; i offset; i$++)$

cout ;

if $($t $==0)$

$\{$

cout #$"$ endl;

return;

$\}$

cout $$ t$->$element $$ endl;

printInternal$($t$->$left, offset $+1)$;

printInternal$($t$->$right, offset $+1)$;

return;

$\}$

$//$ LAB $9$: COMPLETE; to print in$-$line all elements in BST rooted in t;

void printElements$($BinaryNode$*$ t$)$ const

$\{$

if $($t $!=0)$

$\{$

$//$ print the elements of the left subtree

$//$ print the element under pointer t

$//$ print the elements of the right subtree

$\}$

$\}$

$//$ LAB $9$: COMPLETE; returns the number of elements stored in BST

$//$ rooted in t;

$//$ Taking recursive view:

$//(1)$ what is the size of the BST under pointer t if t is a nullptr? $--$ Must

be $0.$

$//(2)$ what is the size of the BST under t if t is not a nullptr?

$//...$ one Node $(*$t$)$ exists $($the one that t points to$)..$ count $1$

$//...$ and add size of the left subtree of $*$t

$//...$ and add size of the right subtree of $*$t

int size$($BinaryNode$*$ t$)$ const

$\{$

return $-1$; $//$ temp PLACE HOLDER for the actual code;

$//$ remove when adding the actual code

$\}$

$\}$;

#endif