title: Binary Search Tree getHeight() function
body: <p>I am attempting to write a function that will return the height of a BST.  I'm writing my code using test-driven development but, unfortunately, it's not passing my test and I can't figure out why.  </p>
  
  <p>I'm passing parts 0, 1, and 2 of my test but am failing at part 3.  Any help in figuring out what is wrong with my code is much appreciated.  Thank you!</p>
  
  <p>Here's some relevant excerpts of my code:</p>
  
  <p><strong>BST.cpp</strong></p>
  
  <pre><code>unsigned BST::Node::getHeight() const{
      unsigned leftSide = 0;
      if(myLeft != NULL){
          myLeft-&gt;getHeight();
      }
      unsigned rightSide = 0;
      if(myRight != NULL){
          myRight-&gt;getHeight();
      }
      if(leftSide &gt; rightSide){
          return leftSide++;
      } else{
          return rightSide++;
      }
  }
  
  unsigned BST::getHeight() const{
      if(myNumItems == 0){
          return 0;
      } else if(myNumItems == 1){
          return 1;
      } else if(myNumItems == 2){
          return 2;
      } else {
          return myRoot-&gt;getHeight();
      }
  }
  </code></pre>
  
  <p><strong>BST.h</strong></p>
  
  <pre><code>class BST {
  public:
      BST();
      virtual ~BST();
      unsigned getHeight() const;
  private:
  struct Node {
      Node(const Item&amp; it);
          virtual ~Node();
          void insert(const Item&amp; it);
          unsigned getHeight() const;
  
          Item myItem;
          Node* myLeft;
          Node* myRight;
  };
  
  Node* myRoot;
  unsigned myNumItems;
  friend class BST_Tester;
  };
  </code></pre>
  
  <p><strong>BST_Tester.cpp</strong></p>
  
  <pre><code>void BST_Tester::testGetHeight() {
  cout &lt;&lt; "Testing getHeight()..." &lt;&lt; flush;
  BST bst;
  // empty
  assert( bst.getHeight() == 0 );
  cout &lt;&lt; " 0 " &lt;&lt; flush;
  // balanced
  bst.insert(44);
  assert( bst.getHeight() == 1 );
  cout &lt;&lt; " 1 " &lt;&lt; flush;
  bst.insert(22);
  assert( bst.getHeight() == 2 );
  cout &lt;&lt; " 2 " &lt;&lt; flush;
  bst.insert(66);
  assert( bst.getHeight() == 2 );
  cout &lt;&lt; " 3 " &lt;&lt; flush;
  bst.insert(77);
  assert( bst.getHeight() == 3 );
  cout &lt;&lt; " 4a " &lt;&lt; flush;
  bst.insert(55);
  assert( bst.getHeight() == 3 );
  cout &lt;&lt; " 4b " &lt;&lt; flush;
  bst.insert(33);
  assert( bst.getHeight() == 3 );
  cout &lt;&lt; " 4c " &lt;&lt; flush;
  bst.insert(11);
  assert( bst.getHeight() == 3 );
  cout &lt;&lt; " 4d " &lt;&lt; flush;
  bst.insert(88);
  assert( bst.getHeight() == 4 );
  cout &lt;&lt; " 4e " &lt;&lt; flush;
  // chained ascending
    BST bst2a;
    bst2a.insert(11);
    bst2a.insert(22);
    bst2a.insert(33);
    bst2a.insert(44);
    bst2a.insert(55);
    bst2a.insert(66);
    bst2a.insert(77);
    assert( bst2a.getHeight() == 7 );
    cout &lt;&lt; " 5a " &lt;&lt; flush;
  // chained descending
    BST bst2b;
    bst2b.insert(77);
    bst2b.insert(66);
    bst2b.insert(55);
    bst2b.insert(44);
    bst2b.insert(33);
    bst2b.insert(22);
    bst2b.insert(11);
    assert( bst2b.getHeight() == 7 );
    cout &lt;&lt; " 5b " &lt;&lt; flush;
  // four 4-node permutations
  BST bst3;
  bst3.insert(44);
  assert( bst3.getHeight() == 1 );
    cout &lt;&lt; " 6a " &lt;&lt; flush;
  bst3.insert(22);
  assert( bst3.getHeight() == 2 );
    cout &lt;&lt; " 6b " &lt;&lt; flush;
  bst3.insert(33);
  assert( bst3.getHeight() == 3 );
    cout &lt;&lt; " 6c " &lt;&lt; flush;
  bst3.insert(55);
  assert( bst3.getHeight() == 3 );
    cout &lt;&lt; " 6d " &lt;&lt; flush;
  BST bst4;
  bst4.insert(44);
  assert( bst4.getHeight() == 1 );
    cout &lt;&lt; " 7a " &lt;&lt; flush;
  bst4.insert(33);
  assert( bst4.getHeight() == 2 );
    cout &lt;&lt; " 7b " &lt;&lt; flush;
  bst4.insert(22);
  assert( bst4.getHeight() == 3 );
    cout &lt;&lt; " 7c " &lt;&lt; flush;
  bst4.insert(55);
  assert( bst4.getHeight() == 3 );
    cout &lt;&lt; " 7d " &lt;&lt; flush;
  BST bst5;
  bst5.insert(44);
  assert( bst5.getHeight() == 1 );
    cout &lt;&lt; " 8a " &lt;&lt; flush;
  bst5.insert(33);
  assert( bst5.getHeight() == 2 );
    cout &lt;&lt; " 8b " &lt;&lt; flush;
  bst5.insert(55);
  assert( bst5.getHeight() == 2 );
    cout &lt;&lt; " 8c " &lt;&lt; flush;
  bst5.insert(66);
  assert( bst5.getHeight() == 3 );
    cout &lt;&lt; " 8d " &lt;&lt; flush;
  BST bst6;
  bst6.insert(44);
  assert( bst6.getHeight() == 1 );
    cout &lt;&lt; " 9a " &lt;&lt; flush;
  bst6.insert(33);
  assert( bst6.getHeight() == 2 );
    cout &lt;&lt; " 9b " &lt;&lt; flush;
  bst6.insert(66);
  assert( bst6.getHeight() == 2 );
    cout &lt;&lt; " 9c " &lt;&lt; flush;
  bst6.insert(55);
  assert( bst6.getHeight() == 3 );
    cout &lt;&lt; " 9d " &lt;&lt; flush;
  cout &lt;&lt; " Passed!" &lt;&lt; endl;
  }
  </code></pre>
  
  <p><strong>Edit:</strong></p>
  
  <p>In case anyone looks at this and is wondering about the answer, I figured it out.  Here is my new code.</p>
  
  <pre><code>unsigned BST::Node::getHeight() const{
      unsigned leftSide = 0;
      if(myLeft != NULL){
          leftSide = myLeft-&gt;getHeight();
      }
      unsigned rightSide = 0;
      if(myRight != NULL){
          rightSide = myRight-&gt;getHeight();
      }
      if(leftSide &gt; rightSide){
          return ++leftSide;
      } else{
          return ++rightSide;
      }
  }
  
  unsigned BST::getHeight() const{
      if(myNumItems == 0){
          return 0;
      } else {
          return myRoot-&gt;getHeight();
      }
  }
  </code></pre>
  
  <p>It was just a matter of flipping leftSide++ to ++leftSide.</p>