Balanced Tree

[Gaiety]

Hi ,

i am using the following function to verify whether a given tree is balanced or not.

its working for some inputs and not working for others

1)    15    

   2)     15 
    10  

    3)      15 
      10           25 

( the above are balanced ok)

                            15
           10                               25
    7              12                16      
              11          14
                    13

( the program is printing the above is balanced)

unable to rectify the probelm.

int isbal(BST_t *root)
{

        if( root )
        {

                hr=height( root -> right);
                hl=height( root -> left );
                if((hr - hl) >= -1 && (hr - hl) <= 1)
                        return 1;
                else
                        return 0;
        }
        else
        {
                return 1;
        }
}

int height(BST_t *root)
{
     if ( root)
      {
         return ( 1 + max( height(root->left), height(root->right)));
      }
   else
   {
       return 0;
   }
}

[Tom Gunn]

Your isbal() function only tests the root, it should recursively test every node because there are trees that can be unbalanced but still have a height difference of less than 2 from the root. The definition of height balanced is that when every node is tested as an individual tree, it will be balanced according to the height rule.

[dkalita]

what he says is correct.
U r only checking for the root.
yor function should be something like

int isbal(BST_t *root)
{
   if( root )
   {

        hr=height( root -> right);
        hl=height( root -> left );
        if(!((hr - hl) >= -1 && (hr - hl) <= 1))
                 return 0;
        else
                 return (isbal(root->left) && isbal(root->right));
    }
    else
    {
         return 1;
     }
}

and also thoroughly check the condition
"if(!((hr - hl) >= -1 && (hr - hl) <= 1))"