write the code in c++

(Binary search tree) Write a function printRange that takes as input a

binary search tree t and two keys, k1 and k2, which are ordered so that k1 < k2, and

print all elements x in the tree such that k1 <= x <= k2.

You can add this function in BinarySearchTree.h (click the link) that we used

in the lecture and lab 7.

public:

void printRange()

{

printRange(root,k1, k2);

}

private:

void printRange(BinaryNode* t, int k1, int k2)

{

// add your code

}

Here are the sample runs:

insert the values (stop when entering 0):

10 5 20 3 22 6 18 7 9 13 15 4 2 1 19 30 8 0

enter the range of values: 8 18

print the values:

8, 9, 10, 13, 15, 18,

// BinarySearchTree.h

#ifndef BINARY_SEARCH_TREE_H

#define BINARY_SEARCH_TREE_H

#include

#include

using namespace std;

template

class BinarySearchTree

{

public:

BinarySearchTree( ) : root{ nullptr }

{

}

~BinarySearchTree( )

{

makeEmpty();

}

bool isEmpty( ) const

{

return root == nullptr;

}

const C & findMin( ) const

{

assert(!isEmpty());

return findMin( root )->element;

}

const C & findMax( ) const

{

assert(!isEmpty());

return findMax( root )->element;

}

bool contains( const C & x ) const

{

return contains( x, root );

}

void printTree( ) const

{

if( isEmpty( ) )

cout << "Empty tree" << endl;

else

printTree( root );

}

void makeEmpty( )

{

makeEmpty( root );

}

void insert( const C & x )

{

insert( x, root );

}

void remove( const C & x )

{

remove( x, root );

}

private:

struct BinaryNode

{

C element;

BinaryNode* left;

BinaryNode* right;

BinaryNode( const C & theElement, BinaryNode* lt, BinaryNode* rt )

: element{ theElement }, left{ lt }, right{ rt }

{ }

};

BinaryNode* root;

// Internal method to find the smallest item in a subtree t.

// Return node containing the smallest item.

BinaryNode* findMin( BinaryNode* t ) const

{

if( t == nullptr )

return nullptr;

if( t->left == nullptr )

return t;

return findMin( t->left );

}

// Internal method to find the largest item in a subtree t.

// Return node containing the largest item.

BinaryNode* findMax( BinaryNode* t ) const

{

if( t != nullptr )

while( t->right != nullptr )

t = t->right;

return t;

}

// Internal method to test if an item is in a subtree.

// x is item to search for.

// t is the node that roots the subtree.

bool contains( const C & x, BinaryNode* t ) const

{

if( t == nullptr )

return false;

else if( x < t->element )

return contains( x, t->left );

else if( t->element < x )

return contains( x, t->right );

else

return true; // Match

}

void printTree( BinaryNode* t) const

{

if( t != nullptr )

{

printTree( t->left);

cout << t->element << " - ";

printTree( t->right);

}

}

void makeEmpty( BinaryNode* & t )

{

if( t != nullptr )

{

makeEmpty( t->left );

makeEmpty( t->right );

delete t;

}

t = nullptr;

}

// Internal method to insert into a subtree.

// x is the item to insert.

// t is the node that roots the subtree.

// Set the new root of the subtree.

void insert( const C & x, BinaryNode* & t )

{

if( t == nullptr )

t = new BinaryNode{ x, nullptr, nullptr };

else if( x < t->element )

insert( x, t->left );

else if( t->element < x )

insert( x, t->right );

else

; // Duplicate; do nothing

}

// Internal method to remove from a subtree.

// x is the item to remove.

// t is the node that roots the subtree.

// Set the new root of the subtree.

void remove( const C & x, BinaryNode* & t )

{

if( t == nullptr )

return; // Item not found; do nothing

if( x < t->element )

remove( x, t->left );

else if( t->element < x )

remove( x, t->right );

else if( t->left != nullptr && t->right != nullptr ) // Two children

{

t->element = findMin( t->right )->element;

remove( t->element, t->right );

}

else

{

BinaryNode* oldNode = t;

if ( t->left == nullptr )

t = t->right;

else

t = t->left;

delete oldNode;

}

}

};

#endif