Generate a Balanced BST

main.cpp

#include <iostream>
#include <vector>
using namespace std;

template<class T>
struct TreeNode{
   T data;
   TreeNode<T> * right;
   TreeNode<T> * left;      
};

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

template <class T> 
int Tree<T>::height(){
   return height(root);
}

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

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

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

template <class T>
void Tree<T>::createTree(const vector<T>& sortedVec) {
   if(root != NULL) { // the root should be null
     return;
   }
   createTree(root, sortedVec, 0, sortedVec.size()-1);   
}

template <class T>
void Tree<T>::createTree(TreeNode<T>*& treeNode, const vector<T>& sortedVec, int start, int end)
{
   if(end < start) {
      return;
   }
   
   int mid = (end + start) / 2;
    
   treeNode = new TreeNode<T>;
   treeNode->data = sortedVec[mid];

   createTree(treeNode->left, sortedVec, start, mid - 1);
   createTree(treeNode->right, sortedVec, mid + 1, end);
}


int main() {

   return 0;
}