Balanced Binary Tree | Leetcode 110 | Optimal and Slightly Optimal Solutions

You are given the root of a binary tree. Your task is to determine whether the tree is height-balanced.

A binary tree is considered height-balanced if, for every node in the tree:

• The height difference between its left and right subtrees is at most 1.
• Both left and right subtrees are also height-balanced.

Here’s the [Problem Link] to begin with.

Example 1

Input: root = [3,9,20,null,null,15,7]

        3
       / \
      9   20
         /  \
        15   7

Output: true

Example 2

Input: root = [1,2,2,3,3,null,null,4,4]

        1
       / \
      2   2
     / \
    3   3
   / \
  4   4

Output: false
Explanation: The left subtree has height 3 more than the right subtree, so it is unbalanced.

Intuition and Approach

To check if a tree is balanced:

1. Compute the height of left and right subtrees for each node.
2. If the absolute difference of heights is greater than 1, the tree is not balanced.
3. To make this efficient, use a special return value -1 to signal imbalance. This allows early termination, avoiding unnecessary work.

We’ll look at two versions:

• Optimal solution – Computes left and right heights, then checks balance.
• Slightly optimal solution – Adds a pruning step by checking left first, and only if it is balanced proceeds to check right.

Optimal Solution

Code Implementation

class Solution:
    def solve(self, node):
        if node is None:
            return 0
        leftH = self.solve(node.left)
        rightH = self.solve(node.right)
        if leftH == -1 or rightH == -1:
            return -1
        if abs(leftH - rightH) > 1:
            return -1
        return 1 + max(leftH, rightH)

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        height = self.solve(root)
        if height == -1:
            return False
        return True

Code Explanation

• Base case: If the node is None, its height is 0.
• Recursively compute leftH and rightH.
• If either subtree is unbalanced (returns -1), propagate -1 upwards.
• If the absolute difference of leftH and rightH exceeds 1, return -1 to mark unbalance.
• Otherwise, return the actual height 1 + max(leftH, rightH).
• isBalanced(root) checks the root result. If -1, return False, else return True.

Slightly Optimal Solution

Code Implementation

class Solution:
    def solve(self, node):
        if node is None:
            return 0
        leftH = self.solve(node.left)
        if leftH == -1:
            return -1
        rightH = self.solve(node.right)
        if rightH == -1:
            return -1
        if abs(leftH - rightH) > 1:
            return -1
        return 1 + max(leftH, rightH)

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        height = self.solve(root)
        if height == -1:
            return False
        return True

Code Explanation

• This version prunes earlier.
• If the left subtree is already unbalanced (-1), it does not bother computing the right subtree.
• Similarly, if the right is unbalanced, it exits early.
• This saves unnecessary recursive calls when imbalance is found in large trees.

Time and Space Complexity

• Time Complexity (both versions):
  Each node is visited once, and at each node we do constant work.
  So time is O(N), where N is the number of nodes.
• Space Complexity:
  The space is due to recursion depth. In the worst case (skewed tree), it can be O(N).
  In the best case (balanced tree), it is O(log N).

Conclusion

The Balanced Binary Tree problem is solved by combining height calculation with an early unbalance detection mechanism:

• The optimal solution calculates both left and right subtree heights first.
• The slightly optimal solution improves efficiency by pruning unnecessary checks as soon as imbalance is detected.

Both approaches run in O(N) time and ensure early stopping when imbalance is found, making them efficient in practice.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.