Height balanced tree

Consider a height-balancing scheme where following conditions should be checked to determine if a binary tree is balanced.
An empty tree is height-balanced. A non-empty binary tree T is balanced if:
1) Left subtree of T is balanced
2) Right subtree of T is balanced
3) The difference between heights of left subtree and right subtree is not more than 1.

Write a function to check if a binary tree is balanced.

Comments

  1. /* Returns true if binary tree with root as root is height-balanced */
    bool isBalanced(struct node *root)
    {
    int lh; /* for height of left subtree */
    int rh; /* for height of right subtree */

    /* If tree is empty then return true */
    if(root == NULL)
    return 1;

    /* Get the height of left and right sub trees */
    lh = height(root->left);
    rh = height(root->right);

    if( abs(lh-rh) <= 1 &&
    isBalanced(root->left) &&
    isBalanced(root->right))
    return 1;

    /* If we reach here then tree is not height-balanced */
    return 0;
    }

    ReplyDelete

Post a Comment

Popular posts from this blog