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:momdadpizzaappleuncleaunt#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->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;}};