title: to find out if a binary tree is balanced or not efficiently
body: <p>A binary tree is said to be height balanced if both its left sub-tree &amp; right sub-tree are balanced and the difference between the height of left sub-tree and right sub-tree is <em>less than or equal to 1.</em></p>
  
  <p>i have to find out if a given binary tree is balanced or not! </p>
  
  <p>based on the above concept i have used the following code:</p>
  
  <pre><code>bool isbalanced(struct node *root)
  {
      int left,right;
      if(root==NULL)
      return true;
      else
      {
          left=height(root-&gt;left);
          right=height(root-&gt;right);
          if(abs(left-right)&lt;=1 &amp;&amp; isbalanced(root-&gt;right)==true &amp;&amp; isbalanced(root-&gt;left)==true)
          return true;
          else
          {
              return false;
          }
      }
  }
  </code></pre>
  
  <p>I have calculated the height using a separate height() function:</p>
  
  <pre><code>int height(struct node *root)
  {
      if(root==NULL)
      return 0;
      int left=height(root-&gt;left);
      int right=height(root-&gt;right);
      if(left&gt;right)
      return 1+left;
      else
      return 1+right;
  }
  </code></pre>
  
  <p>I am getting the correct solution if the tree is balanced or unbalanced. But if the given tree is skewed the time complexity would be O(n^2).</p>
  
  <p>Can there be a method so that i can accomplish this task in a more efficient way?</p>