0

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;
   }
}

Edited by mike_2000_17: Fixed formatting

3
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by dkalita
0

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.

Edited by Tom Gunn: n/a

0

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))"

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.