CODEWITHSUNDEEP
performancealgorithmbinary-tree
poorvank
poorvank

Reputation: 7612

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

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?

Upvotes: 0

Views: 2614

Answers (2)

Fallen
Fallen

Reputation: 4565

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

Upvotes: 3

Ted Hopp
Ted Hopp

Reputation: 234857

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 bookkeeping1) to cut off the right subtree search early in many cases where the overall tree is unbalanced but each subtree is balanced.

1 bookkeeping details are left as an exercise for the reader

Upvotes: 1

Related Questions