title: Balancing String based Binary Search Tree (For Spellchecking)
body: <p><strong>Update:</strong> I can't get "Balancing" to work, because I cannot get "doAVLBalance" to recognize the member functions "isBalanced()", "isRightHeavy()", "isLeftHeavy". And I don't know why! I tried Sash's example(3rd answer) exactly but I get "deceleration is incompatible" and I couldn't fix that...so I tried doing it my way...and it tells me those member functions don't exist, when they clearly do.</p>
  
  <p>"Error: class "IntBinaryTree:TreeNode" has no member "isRightHeavy". 
  I'm stuck after trying for the last 4 hours :(. Updated code below, help would be much appreciated!!</p>
  
  <p>I'm creating a <em>String based Binary Search Tree</em> and need to make it a "Balanced" tree. How do I do this?<em>*</em> Help please!! Thanks in advance!</p>
  
  <p><strong>BinarySearchTree.cpp:</strong></p>
  
  <pre><code>    bool IntBinaryTree::leftRotation(TreeNode *root)
      {
          //TreeNode *nodePtr = root;  // Can use nodePtr instead of root, better?
          // root, nodePtr, this-&gt;?
  
          if(NULL == root)
          {return NULL;}
  
          TreeNode *rightOfTheRoot = root-&gt;right;
          root-&gt;right = rightOfTheRoot-&gt;left;
          rightOfTheRoot-&gt;left = root;
  
          return rightOfTheRoot;
      }
  
      bool IntBinaryTree::rightRotation(TreeNode *root)
      {
          if(NULL == root)
          {return NULL;}
          TreeNode *leftOfTheRoot = root-&gt;left;
          root-&gt;left = leftOfTheRoot-&gt;right;
          leftOfTheRoot-&gt;right = root;
  
          return leftOfTheRoot;
      }
  
      bool IntBinaryTree::doAVLBalance(TreeNode *root)
      {
  
  
          if(NULL==root)
              {return NULL;}
          else if(root-&gt;isBalanced()) // Don't have "isBalanced"
              {return root;}
  
          root-&gt;left = doAVLBalance(root-&gt;left);
          root-&gt;right = doAVLBalance(root-&gt;right);
  
          getDepth(root); //Don't have this function yet
  
          if(root-&gt;isRightHeavy()) // Don't have "isRightHeavey"
          {
              if(root-&gt;right-&gt;isLeftheavey())
              {
                  root-&gt;right = rightRotation(root-&gt;right);
              }
              root = leftRotation(root);
          }
          else if(root-&gt;isLeftheavey()) // Don't have "isLeftHeavey"
          {
              if(root-&gt;left-&gt;isRightHeavey())
              {
                  root-&gt;left = leftRotation(root-&gt;left);
              }
              root = rightRotation(root);
          }
          return root;
      }
  
      void IntBinaryTree::insert(TreeNode *&amp;nodePtr, TreeNode *&amp;newNode)
      {
          if(nodePtr == NULL)
              nodePtr = newNode;                  //Insert node
          else if(newNode-&gt;value &lt; nodePtr-&gt;value)
              insert(nodePtr-&gt;left, newNode);     //Search left branch
          else
              insert(nodePtr-&gt;right, newNode);    //search right branch
      }
  
  //
  // Displays the number of nodes in the Tree
  
  
  int IntBinaryTree::numberNodes(TreeNode *root)
  {
      TreeNode *nodePtr = root;
  
      if(root == NULL)
          return 0;
  
      int count = 1; // our actual node
      if(nodePtr-&gt;left !=NULL)
      { count += numberNodes(nodePtr-&gt;left);
      }
      if(nodePtr-&gt;right != NULL)
      {
          count += numberNodes(nodePtr-&gt;right);
      }
      return count;
  } 
  
      // Insert member function
  
      void IntBinaryTree::insertNode(string num)
      {
          TreeNode *newNode; // Poitner to a new node.
  
          // Create a new node and store num in it.
          newNode = new TreeNode;
          newNode-&gt;value = num;
          newNode-&gt;left = newNode-&gt;right = NULL;
  
          //Insert the node.
          insert(root, newNode);
      }
  
      // More member functions, etc.
  </code></pre>
  
  <p><strong>BinarySearchTree.h:</strong></p>
  
  <pre><code>class IntBinaryTree
  {
  private:
      struct TreeNode
      {
          string value; // Value in the node
          TreeNode *left; // Pointer to left child node
          TreeNode *right; // Pointer to right child node
      };
  
      //Private Members Functions
      // Removed for shortness
      void displayInOrder(TreeNode *) const;
  
  
  public:
      TreeNode *root;
      //Constructor
      IntBinaryTree()
          { root = NULL; }
      //Destructor
      ~IntBinaryTree()
          { destroySubTree(root); }
  
      // Binary tree Operations
      void insertNode(string);
      // Removed for shortness
  
      int numberNodes(TreeNode *root);
      //int balancedTree(string, int, int); // TreeBalanced
  
      bool leftRotation(TreeNode *root);
      bool rightRotation(TreeNode *root);
      bool doAVLBalance(TreeNode *root); // void doAVLBalance();
      bool isAVLBalanced();
  
      int calculateAndGetAVLBalanceFactor(TreeNode *root);
  
      int getAVLBalanceFactor()
      {
          TreeNode *nodePtr = root; // Okay to do this? instead of just
          // left-&gt;mDepth
          // right-&gt;mDepth
  
          int leftTreeDepth = (left !=NULL) ? nodePtr-&gt;left-&gt;Depth : -1;
          int rightTreeDepth = (right != NULL) ? nodePtr-&gt;right-&gt;Depth : -1;
          return(leftTreeDepth - rightTreeDepth);
      }
  
      bool isRightheavey() { return (getAVLBalanceFactor() &lt;= -2); }
  
      bool isLeftheavey() { return (getAVLBalanceFactor() &gt;= 2); }
  
  
      bool isBalanced()
      {
          int balanceFactor = getAVLBalanceFactor();
          return (balanceFactor &gt;= -1 &amp;&amp; balanceFactor &lt;= 1);
      }
  
  
      int getDepth(TreeNode *root); // getDepth
  
      void displayInOrder() const
          { displayInOrder(root); }
      // Removed for shortness
  };
  </code></pre>