Check if Tree is a Balanced Tree

Problem

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one

Solution

Method 1 - Difference of height at each node should not be greater than 1
Here is the code :

public boolean isBalanced(Node root){
    if(root==null){
        return true;  //tree is empty
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();

        if(isBalanced(root.left) && isBalanced(root.right) 
                 && Math.abs(lh-rh) < =1)
        {
            return true;
        }else
            return false;
    }
    return true;
}

Time complexity - O(n^2)
For each node, we are calculating hieght again and again, which takes O(n) time. Hence O(n^2)

FOLLOW UP : 
suppose the tree is massively unbalanced. Like, a million nodes deep on one side and three deep on the other. Is there a scenario in which this algorithm blows the stack? Can you fix the implementation so that it never blows the stack, even when given a massively unbalanced tree?

Optimization - We are seeing that we are again and again calculating the hieght of the tree. This can be done in 1 method itself.

public boolean isHeightBalanced(Node root, out int height)
    if (root == null){
        height = 0
        return true
 }
 int heightLeft=0, heightRight=0;
 //height is set by the isHeightBalanced function
    boolean balance = isHeightBalanced(root.left, heightLeft) && isHeightBalanced(root.right, heightRight);
    height = max(heightLeft, heightRight)+1
    return balance and abs(heightLeft - heightRight) <= 1    
}

Though this looks like a small optimization, but this will save lots of time.
Time complexity - O(n)

Another way to write the above code, without using boolean variable, we can get rid of it and instead return the height. We can check the height of each subtree as we recurse down from the root.
If the subtree is balanced, then the function return actual height of the subtree.
If the subtree is not balanced, then the function returns -1.

public int checkHeight(TreeNode root){
    if(root == null)
        return 0;
 
    int leftHeight = checkHeight(root.left);
    if(leftHeight == -1)
        return -1;  //not balanced
 
    int rightHeight = checkHeight(root.right);
    if(rightHeight == -1)
        return -1;
 
    int heightDiff = Math.abs(leftHeight - rightHeight);
    if(heightDiff > 1)
        return -1;
    else
        return Math.max(leftHeight, rightHeight) + 1;
}
 
public boolean isBalanced(TreeNode root){
    if(checkHeight(root) == -1)
        return false;
    else
        return true;
}

Time Complexity: O(N) - (credits)

Method 2 -Difference between minDepth and maxDepth should be less than 1
 A tree is considered balanced when the difference between the min depth and max depth does not exceed 1.

Recursive algorithms always work well on trees, so here’s some code.

int minDepth( Node * root ) {
    if( !root ) {
        return 0;
    }
    return 1 + min( minDepth( root->left ),
                    minDepth( root->right ));
}

int maxDepth( Node * root ) {
    if( !root ) {
        return 0;
    }
    return 1 + max( maxDepth( root->left ),
                            maxDepth( root->right ));
} 

bool isBalanced( Node * root ) {
    return ( maxDepth( root ) - minDepth( root ) ) <= 1
}

Time complexity- O(n)
For each node we calculate maxDepth - takes O(n) time, and minDepth takes O(n) time, and finally the boolean operation takes O(1) time.