понедельник, 20 июля 2015 г.

Check if the binary tree is balanced


template<typename T>
struct treenode {
 treenode<T> * left, * right;
 T data;
 treenode(const T& param) 
: left(NULL), right(NULL), data(param) {}
};

template<typename T>
bool is_balanced(treenode<T> * node, int& height) {
 if (!node)
  return true;
 ++height;

 if (!is_balanced(node->left, height))
  return false;

 const int lh = height;
 height = 0;

 if (!is_balanced(node->right, height))
  return false;

 const int rh = height;
 return abs(lh - rh) <= 2;
}