I need help writing these functions for my code. In the homework this week you started reading and programming binary search trees. The one missing piece was inserting into a binary search tree; we'll take care of that today and write the insert function, as well as a height function. Both functions will be implemented in the "bst. h" header file, and tested using a provided main program in "main. cpp".Step one is to implement the insert function --- go ahead and modify "bst. h", adding the necessary code to (1) allocate a new node, and (b) link it into the tree. Once you have insert implemented, test your work using Codio's interactive terminal window. In this exercise we are building a tree of strings, with "#" as the sentinel. Example:#Size: 6Inorder: apple aunt dad mom pizza uncleHeight: 3You'll know the tree is built properly if the inorder output is in sorted order --- if not, then your insert function is not linking the new nodes into the tree correctly. Ignore the height for now (which is probably displayed as -1).Once insert is working, step two is to implement the height function in "bst. h". Since height needs to recursively traverse the entire tree, you'll want to take a public-private approach where a private helper function does the actual work of computing the height. Here is the main. cpp:#include #include #include "bst. h"using namespace std;int main(){binarysearchtree tree;string key; 1. Inputs values from the keyboard and builds a binary search// tree; reads input until the sentinel ("#") is input. The// resulting binary search tree is returned.//cin >> key;while (key != "#"){tree. insert(key);cin >> key;} 2. Output size and contents (in order)://cout << "Size: " << tree. size() << endl;tree. inorder(); 3. Output height://cout << "Height: " << tree. height() << endl;// done:return 0;}Here is the bst. h:#pragma once#include #include // std::maxusing namespace std;templateclass binarysearchtree{private:struct NODE{TKey Key;NODE* Left;NODE* Right;};NODE* Root; // pointer to root node of tree (nullptr if empty)int Size; // # of nodes in the tree (0 if empty) _inorder does the actual inorder traversal and output// to console. Each key is output to the console followed// by " ", including the last key.//void _inorder(NODE* cur){if (cur == nullptr)return;else{_inorder(cur-&g t;Left);cout << cur->Key << " ";_inorder(cur->Right);}}public: default constructor: Creates an empty tree.//binarysearchtree(){Root = nullptr;Size = 0;} size: Returns the # of nodes in the tree, 0 if empty.//int size(){return Size;} height Computes and returns height of tree; height of an empty tree is// defined as -1.//int height(){ TODO:// return -1;} search: Searches the tree for the given key, returning true if found// and false if not.//bool search(TKey key){NODE* cur = Root;while (cur != nullptr){if (key == cur->Key) // already in treereturn true;if (key < cur->Key) // search left:{cur = cur->Left;}else{cur = cur->Right;}}//while // if get here, not foundreturn false;} insert Inserts the given key into the tree; if the key has already been insert then// the function returns without changing the tree.//void insert(TKey key){NODE* prev = nullptr;NODE* cur = Root; 1. Search to see if tree already contains key://while (cur != nullptr){if (key == cur->Key) // already in treereturn;if (key < cur->Key) // search left:{prev = cur;cur = cur->Left;}else{prev = cur;cur = cur->Right;}}//while 2. if we get here, key is not in tree, so allocate// a new node to insert: TODO: allocate a new node, store key, initialize// pointer fields: 3. link in the new node: NOTE: cur is null, and prev denotes node where// we fell out of the tree. if prev is null, then// the tree is empty and the Root pointer needs// to be updated. TODO: link in the new node, updating Root// pointer as appropriate 4. update size and we're done:// TODO://} inorder: Performs an inorder traversal of the tree, outputting// the keys to the console.//void inorder(){cout << "Inorder: ";_inorder(Root);cout << endl;}};