Here is my c++ complete bst code. It’s like AVL trees, without rotations. It rebuilds tree when rebalancing is required.

#ifndef TREE_H__
#define TREE_H__

#include <list>
#include <iostream>
#include <cmath>
#include <functional> //less<T> <-> operator<
//you can #include <queue> and #include <stack> but no other STL
using std::list;
using std::cout;
using std::endl;
using std::less;
//function object used for comparison, default value is less
template <typename Comparable, typename Comparator=less<Comparable> >
class Tree
{
public:
  Tree();  //construct an empty tree
  Tree(const list<Comparable>&); //construct complete BST with min height based on list vals
  ~Tree(); //release all dynamically allocated memory
  void construct(const list<Comparable>&); //release own sources and get values from list
  const Comparable* findMin() const; //pointer to element that is minimal wrt Comparator,*implemented*
  const Comparable* findMax() const; //pointer to element that is maximal wrt Comparator,*implemented*
  const Comparable* getAddress(const Comparable&) const; //find pointer to element with given values
  bool contains(const Comparable*) const; //does this element with data exists in tree,*implemented*
  bool isEmpty() const; //is the tree empty,*implemented*
  void insert(const Comparable*); //insert if dereferenced argument's data is not present, update heights of those affected
  void remove(const Comparable*); //delete if dereferenced argument's data is present, update heights of those affected
  /* DO NOT FORGET TO CHECK BALANCE AND REBALANCE TREE IF NOT BALANCED AFTER INSERTION AND DELETION*/
  size_t getSize() const; //accessor to size,*implemented*
  int getHeight() const; //accessor  to height,*implemented*
  bool isBalanced() const; //accessor to balanced,*implemented*
  void print() const; //inorder print of dereferenced pointers held in nodes,*implemented*
  friend class MusicList; //MusicList class can access private parts of Tree
private:
  struct TreeNode  //scope Tree::TreeNode, thus is only public to Tree structure, no non-friend outsiders can see
  {	 	  	  	  	     	    	    	 	
    const Comparable* element; //adress of the item
    TreeNode* left; //pointer to the root of left subtree
    TreeNode* right; //pointer to the root of right subtree
    TreeNode* parent; //pointer to parent node, pay attention to this!
    size_t height; //height >= 0
    //constructor
    TreeNode(const Comparable* el,TreeNode* l, TreeNode* r, TreeNode* p)
    :element(el), left(l), right(r),parent(p)
    {
    }
    //you should separately set height values, no constructor is defined for them
  };
  TreeNode* root; //designated root
  /* isLessThan(const Comparable& lhs, const Comparable& rhs)
  * returns true if lhs<rhs and false otherwise*/
  Comparator isLessThan;
  size_t size; //number of nodes
  bool balanced;
  int myheight;
  /* uncopiable*/
  Tree(const Tree&); //disabled, provide no implementation
  Tree& operator=(const Tree&); //disabled, provide no implementation
  /* private utility functions*/
  TreeNode* sortedListToBST(typename list<Comparable>::const_iterator& , int , int ,int);
  TreeNode* sortedListToBSTtwo(typename list<const Comparable*>::const_iterator& , int , int ,int);
  void constructtwo(list<const Comparable*>& );
  TreeNode* findMin(TreeNode*) const; //recursively find min in (leftward) subtrees
  TreeNode* findMax(TreeNode*) const; //recursively find max in (rightward) subtrees
  void uphe(TreeNode*,int,int );
  int findmyHeight(TreeNode* );
  bool contains(const Comparable*, TreeNode*) const; //recursively search for an item
  TreeNode* traverseuph(TreeNode* t);
  TreeNode* mydelete(TreeNode* ,const Comparable* );
  bool isLeaf(TreeNode*) const; //isLeaf
  bool isFull(TreeNode*) const; //isFull
  void print(TreeNode*) const; //recursive print
  void destroy_tree(TreeNode*);
  int findmid(int);
  int bsttolist(TreeNode* ,list<const Comparable*>& ) ;
  const Comparable* findadd(TreeNode* t,const Comparable& item) const ;
  
   friend class MusicList;
  //define and use more as you may need
  template <typename T>  //templated max
  T max(T x, T y) { return x > y ? x : y; }	 	  	  	  	     	    	    	 	
 
}; //Do not modify method prototypes and data member names


//Below this point you should begin implementing the missing parts
template <typename Comparable, typename Comparator>
Tree<Comparable,Comparator>::Tree(){
  size = 0;
  balanced = 1;
  root=NULL;
}

//Complete the body of the constructor
template <typename Comparable, typename Comparator>
Tree<Comparable,Comparator>::Tree(const list<Comparable>& data){

  root = NULL;
  size = data.size();
  balanced = 1;
    int lstsize = data.size()-1;
    typename list<Comparable>::const_iterator itr=data.begin();
    root = sortedListToBST(itr,0,lstsize,ceil(log2(lstsize+1))-1);
    traverseuph(root);
}
//Complete the body of the constructor
template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::construct(const list<Comparable>& data)
{
if(root!=NULL)
destroy_tree(root);
  root = NULL;
  size = data.size();
  balanced = 1;
    int lstsize = data.size()-1;
    typename list<Comparable>::const_iterator itr=data.begin();
    root = sortedListToBST(itr,0,lstsize,ceil(log2(lstsize+1))-1);
    traverseuph(root);
}	 	  	  	  	     	    	    	 	
template <typename Comparable, typename Comparator>
typename Tree<Comparable,Comparator>::TreeNode*
Tree<Comparable,Comparator>::sortedListToBST(typename list<Comparable>::const_iterator& copylist, int start, int end,int myheight) {
  if (start > end) return NULL;
  int mid =start +  findmid(end-start);
  TreeNode *leftChild = sortedListToBST(copylist, start, mid-1,myheight-1);
  TreeNode *giris = new TreeNode(&(*copylist),NULL,NULL,NULL);
  giris->left = leftChild;
  giris->height = myheight;
  if(leftChild!=NULL)
  leftChild->parent = giris;
  copylist++;
  giris->right = sortedListToBST(copylist, mid+1, end,myheight-1);
  if(giris->right!=NULL)
    giris->right->parent=giris;
  return giris;
}
template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::constructtwo(list<const Comparable*>& data)
{
  root = NULL;
  size = data.size();
  balanced = 1;
    int lstsize = data.size()-1;
    typename list<const Comparable*>::const_iterator itr=data.begin();
    root = sortedListToBSTtwo(itr,0,lstsize,ceil(log2(lstsize+1))-1);
    traverseuph(root);
}
template <typename Comparable, typename Comparator>
typename Tree<Comparable,Comparator>::TreeNode*
Tree<Comparable,Comparator>::sortedListToBSTtwo(typename list<const Comparable*>::const_iterator& copylist, int start, int end,int myheight) {
  if (start > end) return NULL;
  int mid =start +  findmid(end-start);
  TreeNode *leftChild = sortedListToBSTtwo(copylist, start, mid-1,myheight-1);
  TreeNode *giris = new TreeNode((*copylist),NULL,NULL,NULL);
  giris->left = leftChild;
  giris->height = myheight;
  if(leftChild!=NULL)
  leftChild->parent = giris;
  copylist++;
  giris->right = sortedListToBSTtwo(copylist, mid+1, end,myheight-1);
  if(giris->right!=NULL)
    giris->right->parent=giris;
  return giris;
}	 	  	  	  	     	    	    	 	

template <typename Comparable, typename Comparator>
int Tree<Comparable,Comparator>::findmid(int n){
  int myh;
  int mid;
  n=n+1;
  myh=(log2(n+1));
  int x=pow(2,myh+1)-1;
  if(x>n){
    int nodeatmaxheight=pow(2,myh);
    int premax=pow(2,myh)-1;
    int artik= n-premax;
    if(artik>nodeatmaxheight/2)
      mid=premax/2+nodeatmaxheight/2;
    else
      mid=premax/2+artik;
  } else {
      mid = n/2;
  }
  return mid;
}

template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::destroy_tree(TreeNode* t)
{
  if(t!=NULL)
  {
      destroy_tree(t->left);
      destroy_tree(t->right);
      if(t->left==NULL and t->right==NULL)
      delete t;
  }
}


template <typename Comparable, typename Comparator>
Tree<Comparable,Comparator>::~Tree()
{	 	  	  	  	     	    	    	 	
  destroy_tree(root);
}

template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::uphe(TreeNode* t,int lh,int rh){ //update heights when new node inserted
  if((t->left==t->parent->left and lh>rh) or (t->right==t->parent->right and rh>lh) or rh==lh){
  t=t->parent;
  while(t->parent!=NULL){ //update heights up to root
    t->height=t->height+1;
    t=t->parent;
  }
  t->height = t->height+1;
  }
  int rooth = findmyHeight(root);
  root->height=rooth;
}
template <typename Comparable, typename Comparator>
int Tree<Comparable,Comparator>::findmyHeight(TreeNode* t) {
    if (t == NULL) {
        return -1;
    }
    int lefth = findmyHeight(t->left);
    int righth = findmyHeight(t->right);
    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}
template <typename Comparable, typename Comparator>
typename Tree<Comparable,Comparator>::TreeNode*
Tree<Comparable,Comparator>::traverseuph(TreeNode* t) {
  if(t==NULL)
    return NULL;
  t->height=findmyHeight(t);
  if(t->left != NULL )
    t->left->parent = t;
  if(t->right != NULL )
    t->right->parent = t;
  traverseuph(t->left);
  traverseuph(t->right);
  return NULL;
}	 	  	  	  	     	    	    	 	

template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::insert(const Comparable* data)
{
  if(!contains(data)){
  TreeNode* leaf;
  leaf = root;
  int lhh,rhh;
  if(root!=NULL){
  lhh=findmyHeight(root->left);
    rhh=findmyHeight(root->right);
  }
  if(root){
        while(leaf->right != NULL or leaf->left != NULL){
          if(isLessThan(*data,*(leaf->element))){
          if(leaf->left == NULL)
            break;
          leaf = leaf->left;
          }
          else{
          if(leaf->right == NULL)
            break;
          leaf = leaf->right;
          }
        }
        if(isLessThan(*data,*(leaf->element)))
        {
        leaf->left=new TreeNode(&(*data),NULL,NULL,leaf);
        leaf->left->height=0;
        uphe(leaf->left,lhh,rhh); 
        } else {
        leaf->right=new TreeNode(&(*data),NULL,NULL,leaf);
        leaf->right->height=0;
        uphe(leaf->right,lhh,rhh); 
        }
        size++;
  } else {	 	  	  	  	     	    	    	 	
    root = new TreeNode(&(*data),NULL,NULL,leaf);
    root->height = 0;
    size++;
  }
  //imbalance check
  if(size>1){
  int imb = findmyHeight(root)>=2*floor(log2(size));
  if(imb){
  list<const Comparable*> mlist;  
  bsttolist(root,mlist);
  destroy_tree(root);
  constructtwo(mlist);
  } else {
    traverseuph(root);
  }
  }
  }
} 
template <typename Comparable, typename Comparator>
int Tree<Comparable,Comparator>::bsttolist(TreeNode* t, list<const  Comparable*>& copylist) 
{
  if(t==NULL)
    return -1;
  bsttolist(t->left,copylist);
  copylist.push_back(t->element);
  bsttolist(t->right,copylist);
  return -1;
}
template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::remove(const Comparable* data)
{
  if(contains(data)){
    if(size==1 and (!isLessThan(*data,*root->element) and !isLessThan(*(root->element),*data))){
      delete root;
      size =0;
      balanced=1;
      root=NULL;    
    }else {	 	  	  	  	     	    	    	 	
    size--;
  root = mydelete(root,data);
  traverseuph(root);
  root ->parent = NULL;
    if(size>1){
  int imb = findmyHeight(root)>=2*floor(log2(size));
  if(imb){
  list<const Comparable*> mlist;  
  bsttolist(root,mlist);
  destroy_tree(root);
  constructtwo(mlist);
  } 
  }
    }
      //postorder(root); 
  }
}


template <typename Comparable, typename Comparator>
typename Tree<Comparable,Comparator>::TreeNode*
Tree<Comparable,Comparator>::mydelete(TreeNode* root,const Comparable* data) {

  if(root==NULL) return NULL;
  if(isLessThan(*data,*root->element))
    root->left = mydelete(root->left,data);
  else if(isLessThan(*root->element,*data))
    root->right = mydelete(root->right,data);
  else {
    if(root->left==NULL){
      TreeNode * temp = root->right;
      delete root;
      return temp;
    }
    else if(root->right==NULL){
      TreeNode * temp = root->left;
      delete root;
      return temp;
    }	 	  	  	  	     	    	    	 	
    TreeNode * temp = findMin(root->right);
    root->element = temp->element;
    root->parent = NULL;
    root->right = mydelete(root->right,temp->element);
  }
  root->parent = NULL;
  return root;
}



template <typename Comparable, typename Comparator>
const Comparable* Tree<Comparable,Comparator>::getAddress(const Comparable& item) const
{ 
  return findadd(root,item);
}

template <typename Comparable, typename Comparator>
const Comparable* Tree<Comparable,Comparator>::findadd(TreeNode* t,const Comparable& item) const 
{
    if(t == NULL)
    return NULL;
  else if(isLessThan(item,(*t->element)))
    return findadd(t->left,item);
  else if(isLessThan((*t->element),item))
    return findadd(t->right,item);
  else
    return &(*t->element);
}

template <typename Comparable, typename Comparator>
bool Tree<Comparable,Comparator>::contains(const Comparable* item) const
{  
  return contains(item, root);
}

template <typename Comparable, typename Comparator>
size_t Tree<Comparable,Comparator>::getSize() const
{	 	  	  	  	     	    	    	 	
  return size;
}

template <typename Comparable, typename Comparator>
int Tree<Comparable,Comparator>::getHeight() const
{
  if(isEmpty())
    return -1;  //convention: empty tree has height -1
  else
    return root->height; //>= 0
}

template <typename Comparable, typename Comparator>
bool Tree<Comparable,Comparator>::isEmpty() const
{
  return (root == NULL);
}

template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::print() const
{
  print(root);
  cout << endl;  
}

template <typename Comparable, typename Comparator>
bool Tree<Comparable,Comparator>::isBalanced() const
{
  return balanced;
}

template <typename Comparable, typename Comparator>
const Comparable* Tree<Comparable,Comparator>::findMin() const
{
  if(isEmpty())
    return NULL;
  return findMin(root)->element; //call in to recursive utility function
}	 	  	  	  	     	    	    	 	

template <typename Comparable, typename Comparator>
const Comparable* Tree<Comparable,Comparator>::findMax() const
{
  if(isEmpty())
    return NULL;
  return findMax(root)->element;
}

/* private utility functions 
* define and use as many as you deem required
* some are provided for the already implemented 
* part of the public interface
*/
template <typename Comparable, typename Comparator>
typename Tree<Comparable,Comparator>::TreeNode*
Tree<Comparable,Comparator>::findMin(TreeNode* t) const
{
  if(t == NULL)
    return NULL;

  if(t->left == NULL)
    return t;

  return findMin(t->left);
}

template <typename Comparable, typename Comparator>
typename Tree<Comparable,Comparator>::TreeNode*
Tree<Comparable,Comparator>::findMax(TreeNode* t) const
{
  if(t != NULL)
    while(t->right != NULL)
      t = t->right;
  return t;
}	 	  	  	  	     	    	    	 	

template <typename Comparable, typename Comparator>
bool Tree<Comparable,Comparator>::contains(const Comparable* item,TreeNode* t) const
{
  if(t == NULL)
    return false;
  else if(isLessThan(*item,*(t->element)))
    return contains(item, t->left);
  else if(isLessThan(*(t->element),*item))
    return contains(item, t->right);
  else
    return true;
}

template <typename Comparable, typename Comparator>
bool Tree<Comparable,Comparator>::isLeaf(TreeNode* t) const
{
  return ((t->left == NULL)&& (t->right == NULL));
}

template <typename Comparable, typename Comparator>
bool Tree<Comparable,Comparator>::isFull(TreeNode* t) const
{
  return ((t->left != NULL)&& (t->right != NULL));
}

template <typename Comparable, typename Comparator>
void Tree<Comparable,Comparator>::print( TreeNode * t ) const
{
  if( t && t->left != NULL )
  {
    cout << '[';
    print( t->left );
  }
  else if( t && t->left == NULL && t->right != NULL )
  {	 	  	  	  	     	    	    	 	
    cout << "[";
  }
  if( t != NULL )
  {
    if( isLeaf( t ))
    {
      cout << '(' << *( t->element ) << ')';
    }
    else if( !isLeaf( t ) )
    {
      cout << *( t->element );
    }
  }
  if( t && t->right != NULL )
  {
    print( t->right );
    cout << ']';
  }
  else if( t && t->left != NULL && t->right == NULL )
  {
    cout << "]";
  }
}

#endif