to find out if a binary tree is balanced or not efficiently

Question

A binary tree is said to be height balanced if both its left sub-tree & right sub-tree are balanced and the difference between the height of left sub-tree and right sub-tree is less than or equal to 1.

i have to find out if a given binary tree is balanced or not!

based on the above concept i have used the following code:

bool isbalanced(struct node *root)
{
    int left,right;
    if(root==NULL)
    return true;
    else
    {
        left=height(root->left);
        right=height(root->right);
        if(abs(left-right)<=1 && isbalanced(root->right)==true && isbalanced(root->left)==true)
        return true;
        else
        {
            return false;
        }
    }
}

I have calculated the height using a separate height() function:

int height(struct node *root)
{
    if(root==NULL)
    return 0;
    int left=height(root->left);
    int right=height(root->right);
    if(left>right)
    return 1+left;
    else
    return 1+right;
}

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

Can there be a method so that i can accomplish this task in a more efficient way?

Fallen · Accepted Answer · 2013-07-07 19:47:08Z

3

Considering the given tree as a rooted tree we can calculate the height of all nodes with a single Depth First Search on the given tree. Sketch of the proposed solution:

int isbalanced(struct node *root)
{
    int left,right;
    if(root==NULL)
    return 0;
    else 
    {
        left=isbalanced(root->left);
        right=isbalanced(root->right);
        if(left==-1||right==-1||fabs(left-right)>1){
          return -1;  // it indicates the tree rooted at root or below is imbalanced
        }else{
          return max(right,left)+1;
        }
    }
}

The tree is imbalanced if the function stated above returns -1, balanced otherwise. It doesn't need the height function.

Runtime: O(V+E)

Please note: code not tested

answered Jul 7, 2013 at 19:47

Fallen

4,5833 gold badges30 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ted Hopp · Accepted Answer · 2013-07-07 19:42:27Z

1

You are traversing the left and right subtrees twice: once to get their height and again to test whether they are balanced. You can eliminate half the work by using a structure that contains both the height and a balanced flag, passing one structure down to be filled in by the left subtree and another by the right.

You can then improve on this even more by using the information from the left subtree when scanning the right (or vice versa). The left subtree information can be used (with appropriate bookkeeping¹) to cut off the right subtree search early in many cases where the overall tree is unbalanced but each subtree is balanced.

¹ _{bookkeeping details are left as an exercise for the reader}

answered Jul 7, 2013 at 19:42

Ted Hopp

235k48 gold badges412 silver badges533 bronze badges

Collectives™ on Stack Overflow

to find out if a binary tree is balanced or not efficiently

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related