Member Avatar for 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;
   }
}
Edited by mike_2000_17 because: Fixed formatting
  • 3 Contributors
  • 2 Replies
  • 109 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by dkalita
Member Avatar for 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.

Edited by Tom Gunn because: n/a
Member Avatar for 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))"

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.