Finish this insert function, using tst class given:

E#include #include #include #include "tst.h" using namespace std; insert - public // given a new key and data, allocates and populates a new node // When the tree is empty, makes the new node the root // When the tree is not empty, inserts the new node into the root // (parent of root is NULL) void tst::insert(int k, string s) public insert private // given: pointer to a newly-allocated and populated node to insert pointer to the tree/subtree into which the new node is to be inserted pointer to the parent of r. The parent's right or left child will need to be modified if this is a "duplicate" key, as the new node replaces the current node (r) in the tree. void tst::insert (node * p, node * r, node * rParent) // if the new node's key is LESS THAN r's key, // insert new node on the LEFT side of r. if (p->key key) != { NULL) if (r->left // r already has a left child //WRITE THIS LINE! // else r has no left child /WRITE THIS LINE! // insert new node into r's left child else // make p the new left child else if (p->keyr>key) /FINISH THIS!! else insertEqual(p, r, rParent); // insert()