Help implement BST. The code must follow the instruction below as well as produce the correct output when testing with the input file I'll provide at the end. Please fill-in the TODO parts in the bst.cc code:

INSTRUCTIONS:

3. First, implement the BST (declared in bst.h) and use the unittest_bst() function to test it. DO NOT CHANGE THIS CODE FOR YOUR SUBMISSION, as it will be used to test your code against the answers (with different seed values).

4. Implement the DB and use the unittest_db() function to test it. DO NOT CHANGE THIS CODE FOR YOUR SUBMISSION, as it will be used to test your code against the answers (with different input files).

a) The student ID should be the base class's key member.

b) The student ID should be automatically assigned such that the ID/key should be n if the student is the nth student to join the school. If the student later leaves (i.e., deleted from the BST), the ID does NOT get reassigned to another student. Thus, the student ID of the last student to join the school should reflect the TOTAL number of students that have joined this school since its reception (regardless of whether some have left).

5. Test your code against the provided input and output files.

a) The provided answer for the BST unit test is in "unittest_ans_t100_s100.txt". The s100 refers to the seed of 100 (-s 100), and t100 refers to the number of elements to add to the BST (-t 100).

b) The provided answer for the DB is in "students_1_ans.txt" for the "students_1.txt" input file.

6. Make sure your code has no memory leaks (using valgrind).

7. Your code should work beyond the provided unit tests. That is, even if it does work for all the given tests, if the code has an identifiable bug (i.e., by reading the source code), points WILL be deducted.

For example, if I were to change

unittest_bst(num_test, seed, cout, 5); ->

unittest_bst(num_test, seed, cout, 100);

it should still work.

BST.H

#ifndef BST_H_

#define BST_H_

#include

using namespace std;

class Node {

private:

int key;

Node* parent;

Node* left;

Node* right;

public:

// Default constructor

Node();

// Constructor

Node(int in);

// Destructor

// a virtual constructor is required for inheritance

virtual ~Node();

// Add to parent of current node

void add_parent(Node* in);

// Add to left of current node

void add_left(Node* in);

// Add to right of current node

void add_right(Node* in);

// Get key

int get_key();

// Get parent node

Node* get_parent();

// Get left node

Node* get_left();

// Get right node

Node* get_right();

virtual void print_info(ostream& to);

};

class BST {

private:

Node* root;

// Walk the subtree from the given node

void inorder_walk(Node* in, ostream& to);

// Get the minimum node from the subtree of given node

Node* get_min(Node* in);

// Get the maximum node from the subtree of given node

Node* get_max(Node* in);

public:

// Constructor and Destructor

BST();

~BST();

// Modify tree

void insert_node(Node* in);

void delete_node(Node* out);

// Find nodes in the tree

Node* tree_min(); // minimum key value

Node* tree_max(); // maximum key value

Node* get_succ(Node* in); // successor for a given node

Node* get_pred(Node* in); // predecessor for a given node

void walk(ostream& to); // Traverse the tree from min to max recursively

Node* tree_search(int search_key);

};

#endif

COMLPETE THIS PART, BST.CC

#include "bst.h"

// ---------------------------------------

// Node class

// Default constructor

Node::Node() {

// TODO: Implement this

}

// Constructor

Node::Node(int in) {

// TODO: Implement this

}

// Destructor

Node::~Node() {

// TODO: Implement this

}

// Add parent

void Node::add_parent(Node* in) {

// TODO: Implement this

}

// Add to left of current node

void Node::add_left(Node* in) {

// TODO: Implement this

}

// Add to right of current node

void Node::add_right(Node* in) {

// TODO: Implement this

}

// Get key

int Node::get_key()

{

// TODO: Implement this

}

// Get parent node

Node* Node::get_parent()

{

// TODO: Implement this

}

// Get left node

Node* Node::get_left()

{

// TODO: Implement this

}

// Get right node

Node* Node::get_right()

{

// TODO: Implement this

}

// Print the key to ostream to

// Do not change this

void Node::print_info(ostream& to)

{

to << key << endl;

}

// ---------------------------------------

// ---------------------------------------

// BST class

// Walk the subtree from the given node

void BST::inorder_walk(Node* in, ostream& to)

{

// TODO: Implement this

}

// Constructor

BST::BST()

{

// TODO: Implement this

}

// Destructor

BST::~BST()

{

// TODO: Implement this

}

// Insert a node to the subtree

void BST::insert_node(Node* in)

{

// TODO: Implement this

}

// Delete a node to the subtree

void BST::delete_node(Node* out)

{

// TODO: Implement this

}

// minimum key in the BST

Node* BST::tree_min()

{

// TODO: Implement this

}

// maximum key in the BST

Node* BST::tree_max()

{

// TODO: Implement this

}

// Get the minimum node from the subtree of given node

Node* BST::get_min(Node* in)

{

// TODO: Implement this

}

// Get the maximum node from the subtree of given node

Node* BST::get_max(Node* in)

{

// TODO: Implement this

}

// Get successor of the given node

Node* BST::get_succ(Node* in)

{

// TODO: Implement this

}

// Get predecessor of the given node

Node* BST::get_pred(Node* in)

{

// TODO: Implement this

}

// Walk the BST from min to max

void BST::walk(ostream& to)

{

// TODO: Implement this

}

// Search the tree for a given key

Node* BST::tree_search(int search_key)

{

// TODO: Implement this

}

// ---------------------------------------

INPUT FILE:

Noel Cummings 83 Kian Avery 86 Eliana Knox 77 Paisley Peck 15 Michael Mcgrath 93 Makayla Dixon 35 Mara Singh 86 Aaliyah Arias 92 Hector Nicholson 49 Leo Holder 21 Dangelo Ball 62 Dario Kaufman 27 Brett Ho 90 Jamarcus Castro 59 Sheldon Burnett 63 Van Bautista 26 Gabriel Kelley 40 Kristin Walker 26 Stephany Figueroa 72 Carsen Mullen 36 Wendy Singh 11 Ava Carlson 68 Vaughn Boone 67 Grant Simpson 29 Urijah Oneal 82 Melissa Larson 30 Javier George 62 Roland Walters 23 Brooklyn Mcpherson 67 Cayden Mccarthy 35 Dixie Parrish 29 Jaslyn Hinton 2 Rory Hahn 22 Diamond Lawson 58 Jasper Franco 69 Kendal Wheeler 67 Odin Browning 93 Kenna Benson 56 Reese Walters 11 Thalia Tran 42 Chad Horton 29 Asher Cardenas 73 Angel Finley 21 Charlotte Gray 19 Delilah Hoover 84 Drew Mckenzie 37 Brandon Mahoney 98 Cristian Chandler 24 Leonel Briggs 15 Gracie Buchanan 70