#include <iostream>

using namespace std;

struct BTreeNode {
  int m_nValue;
  BTreeNode *m_pLeft;
  BTreeNode *m_pRight;
};

int getTreeDepth(BTreeNode *pNode) {

  if(pNode==NULL)
    return 0;

  int dLeft = getTreeDepth(pNode->m_pLeft);
  int dRight = getTreeDepth(pNode->m_pRight);

  return (dLeft>dRight?dLeft+1:dRight+1);
}

bool isBalanced(BTreeNode *pRoot) {

  if(pRoot==NULL)
    return true;

  int dLeft = getTreeDepth(pRoot->m_pLeft);
  int dRight = getTreeDepth(pRoot->m_pRight);

  int diff = dLeft-dRight;
  if(diff>1 || diff<-1)
    return false;

  return isBalanced(pRoot->m_pLeft) && isBalanced(pRoot->m_pRight);
}

bool isBalanced(BTreeNode *pNode, int *depth) {
  if(pNode==NULL) {
    depth=0;
    return true;
  }

  int left, right;
  if(isBalanced(pNode->m_pLeft, &left) && isBalanced(pNode->m_pRight, &right)) {
    int diff = left-right;
    if(diff<=1 && diff>=-1) {
      *depth = 1 + (left>right?left:right);
      return true;
    }
  }

  return false;
}

bool isBalanced2(BTreeNode *pNode) {
  int depth=0;
  return isBalanced(pNode, &depth);
}

int main(int argc, char **argv) {

  return 0;
}