110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Solution1:

To check if a tree is height-balanced, get the height of left and right subtrees.

Return true if difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false.

Part 1: getHeightOfTree

heightOf(Left Tree) -> heightOf(Right Tree) -> Max(LeftHeight, RightHeight)+1, for the root and return -> call recursively

public int getHeightOfTree(TreeNode root)
    {
        if(root == null)
        {
            return 0;
        }

        return 1 + Math.max(getHeightOfTree(root.left), getHeightOfTree(root.right));
    }

Part 2: The difference between left and right subtrees, not more than 1, and then recursion

public boolean isBalanced(TreeNode root) {

    if(root == null)
    {
        return true;
    }

    int leftHeight = heightOfTree(root.left);
    int rightHeight = heightOfTree(root.right);

    if(Math.abs(leftHeight-rightHeight) <=1 && isBalanced(root.left) && isBalanced(root.right))
    {
        return true;
    }

    return false;
}

Time/Space complexity: O(n^2)

since for each node, we go through its entire subtrees by calling getHeight repeatedly on the same nodes.

Solution2: More efficient

Make

1. getHeightOfTree both check if the tree is balance
2. check its height

at the same time.

-> Return -1, when it's unbalanced.

So we will immediately break and return -1 from the current call, if the subtree is not balanced.

public int checkHeight(TreeNode root)
{
    if(root == null)
    {
        return 0;
    }

    /*improve the efficiency
    *
    */

    int leftHeight = checkHeight(root.left);
    if(leftHeight == -1)
    {
        return -1;
    }

    int rightHeight = checkHeight(root.right);
    if(rightHeight == -1)
    {
        return -1;
    }

    int heightDifference = Math.abs(leftHeight-rightHeight);

    if(heightDifference > 1)
    {
        return -1;
    }
    else
    {
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

public boolean isBalanced(TreeNode root) {

    if(checkHeight(root) == -1)
    {
        return false;
    }
    else
    {
        return true;
    }
}