22.4 Generate a Balanced BST

Given a sorted vector, generate a binary search tree (BST) with minimal height BST. Feel free to write other helper functions if you need.

Please put the answer in BOLD.

#include #include using namespace std;

template struct TreeNode{ T data; TreeNode * right; TreeNode * left; };

template class Tree{ public: void createTree(const vector& sortedVec); // Implement this below void fillVectorWithInorderTraverse(vector& vec); int height(); private: int height(TreeNode * node); TreeNode* root; void fillVectorWithInorderTraverse(TreeNode* treeNode,vector& vec); };

template int Tree::height(){ return height(root); }

template int Tree::height(TreeNode * node){ if(node == NULL) return -1; return max(height(node->left), height(node->right)) + 1; }

template void Tree::fillVectorWithInorderTraverse(vector& vec){ if(root == NULL) return; fillVectorWithInorderTraverse(root, vec); }

template void Tree::fillVectorWithInorderTraverse(TreeNode* treeNode,vector& vec){ if(treeNode == NULL) return; fillVectorWithInorderTraverse(treeNode->left, vec); vec.push_back(treeNode->data); fillVectorWithInorderTraverse(treeNode->right, vec); }

template void Tree::createTree(const vector& sortedVec) { // IMPLEMENT HERE }

int main() {

return 0; }