Balanced Binary Tree

Problem Statement

LeetCode-110: Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Approach

Based on the definition of a height balanced binary tree, following is a high level approach to solve this problem:

1. Calculate height of left and right subtree at every level.
2. Keep track of the maximum difference of the left and right subtree heights at every level.
3. Once all the nodes are visited, if the maximum difference of left and right subtrees at any level is more than 1, the tree is NOT a height balanced binary tree.

Implementation

Following is a java implementation of the above mentioned approach:

private int maxHeightDifference = Integer.MIN_VALUE;
public boolean isBalanced(TreeNode root) {
    if(null == root){
        return true;
    }
    calculateHeightDifferenceViaDFS(root);
    return maxHeightDifference <= 1;
}
private int calculateHeightDifferenceViaDFS(TreeNode root){
    if(null == root){
        return 0;
    }
    int left = calculateHeightDifference(root.left);
    int right = calculateHeightDifference(root.right);
    maxHeightDifference = Math.max(maxHeightDifference, Math.abs(left-right));
    return 1 + Math.max(left, right);
}

Complexity Analysis

As each node of the tree is processed once, the overall complexity of this algorithm is \(O(n)\) where \(n\) is the number of nodes in the tree.