110.balanced-binary-tree.md

110. Balanced Binary Tree

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.

Clarification Questions

• Is the empty tree balanced?

Test Cases

Normal Cases

Input: 
        1
      /   \
     2     2
          / \
         3   4
Output: True

Input: 
        1
      /   \
     2     2
            \
             4
Output: False

Edge / Corner Cases

Input: 
        1
      /   \
     2     2
    /       \
   5         4
Output: True

Input: 
        1
      /   \
     2     2
    /       \
   5         4
  /           \
 6             7
Output: False

Input:
        1
      /   \
     2     2
    /     / \
   1     3   4
  /     /
 0     5
      /
     6
Output: False

Top-Down Recursion

We can iterate each node recursively to check if the height of their subtree differs <= 1. For each node, we calculate the height of subtree (one recursion), and check the current difference with the check of two subtrees recursively (another recursion).

fun isBalanced(root: TreeNode?): Boolean {
    if (root == null) return true
    val leftHeight = getHeight(root?.left)
    var rightHeight = getHeight(root?.right)
    val diff = leftHeight - rightHeight
    return diff * diff <= 1 && isBalanced(root?.left) && isBalanced(root?.right)
}

private fun getHeight(node: TreeNode?): Int {
    return if (node == null) 0
    else {
        1 + maxOf(getHeight(node?.left), getHeight(node?.right))
    }
}

• Time Complexity: Calculate the height takes O(h), and we have to calculate every node n, total takes O(n * h), in the average case (every node has children) we have O(n log n), but the worst case is O(n^2) when the tree is skewed because the height becomes O(n).
• Space Complexity: O(n) for recursive call stack.

We can calculate the height and store it, then traversal to check. That would be O(n) time and space complexity.

Bottom-Up Solution (Optimal)

From previous solution, we invoke isBalanced() for each node recursively, and for each isBalanced() we have to calculate the height getHeight() recursively which leads to O(n^2) time complexity. Here we can optimize the solution by changing (merging) the purpose of getHeight(). We still use getHeight() to calculate the height, and use this function to indicate if the subtree is height-balanced at the same time.

• If it's height-balanced, then return the height of current subtree.
• Otherwise, just return -1 to indicate unbalanced. If it's not balanced from its child node, then the current node is not balanced as well.

Source: Solution

fun isBalanced(root: TreeNode?): Boolean {
    return getHeight(root) != -1
}

private fun getHeight(root: TreeNode?): Int {
    if (root == null) return 0
    
    val leftHeight = getHeight(root.left)
    val rightHeight = getHeight(root.right)
    
    // If one of the subtrees is not balanced, the it's not balanced overall
    if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) return -1
    else return 1 + max(leftHeight, rightHeight)
}

• Time Complexity: It becomes O(n) since we calculate the height only once for every node.
• Space Complexity: O(n).