logic check of a function to find if a tree is balanced or unbalanced

Question

I am reading the Coding book and one of the questions asks to write a function that checks if a binary tree height is balanced or not. For example, if a tree's right subtree has a height of 4 (meaning its depth is 4) and the left subtree has a depth of 6 then it not balanced but if it's off by 1 then it's ok.

So I've implemented this logic:

int FindNodeHeight(BTNode<int>* node) {

    if(!node)  return 0;
    return std::max(FindNodeHeight(node->lhs), FindNodeHeight(node->rhs)) + 1;
}

bool IsTreeBalanced(BinarySearchTree<int>* root) {

    int left = FindNodeHeight(root->root.lhs);
    int right = FindNodeHeight(root->root.rhs);

    std::cout << "left: " << left << " - right: " << right << std::endl;

    if(std::abs(left - right) > 1) {
        return false;
    }

    return true;
}

But I think it may be wrong based on the solutions explanation but I can't see why. Here are the classes simplified:

template <typename T>
// Binary Tree Node
class BTNode {
public:
    T data;
    BTNode* lhs;
    BTNode* rhs;

    BTNode() {
        lhs = NULL;
        rhs = NULL;
    }
};

template <typename T>
class BinarySearchTree {
public:
    BTNode<T> root;
};

And here is the main where the graph is created and the function is called:

BinarySearchTree<int>* t_unbalanced = new BinarySearchTree<int>();
t_unbalanced->root.data = 1;
t_unbalanced->root.lhs = new BTNode<int>(2);
t_unbalanced->root.rhs = new BTNode<int>(3);
t_unbalanced->root.rhs->rhs = new BTNode<int>(4);
t_unbalanced->root.rhs->rhs->rhs = new BTNode<int>(5);

if(IsTreeBalanced(t_unbalanced)) {
    cout << "Tree is balanced" << endl;
}
else {
    cout << "Tree is unbalanced" << endl;
}

Answer 1

Consider the following case:

            x
           / \
          x   x
         /     \
        x       x
       /         \
      x           x
     /             \
    .               .
   .                 .
  .                   .
 /                     \
x                       x

Your algorithm states that the tree is balanced because the height of the left tree is equal to the height of the right tree. However the height of the tree is n/2=theta(n)!=O(log(n)). Therefore the tree is not balanced.

Balanced search trees are trees whose height in the worst case is O(logn) and for which the operations INSERT, DELETE, and SEARCH can be implemented in time O(logn).

See source.