avl tree

//solution = chainLength is 3
std::string backtrack(Node * x, std::string state){
  if(x->left){
    backtrack(x->left, state + 'L');
  }

  if(state.length() == 3){
    return state.substr(0, 2);
  }

  if(x->right){
    backtrack(x->right, state + 'R');
  }
}

  //
  // Check if node x is unbalanced (i.e., the heights of its
  // two children differ by more than one).  If it is, rebalance
  // at x using one of rotateLeft, rotateRight, doubleRotateLeft,
  // or doubleRotateRight, whichever is appropriate.
  //
void balance( Node *& x ) {
  int balance = -1;

  if(x){
    int leftHeight = ( x->left ? x->left->height : -1 );
    int rightHeight = ( x->right ? x->right->height : -1 );
    balance = leftHeight - rightHeight;
  }

  bool isBalanced = abs(balance) <= 1;

  if(isBalanced){
    return;
  }

  std::string myCase = backtrack(x, "");

  if(myCase == "LL"){
    rotateRight(x);
  }
  if(myCase == "LR"){
    doubleRotateRight(x);
  }
  if(myCase == "RL"){
    doubleRotateLeft(x);
  }
  if(myCase == "RR"){
    rotateLeft(x);
  }
}