Balanced Binary Tree

Difficulty: Easy | Acceptance: 58.30% | Paid: No Topics: Tree, Depth-First Search, 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 left and right subtrees of every node differ in height by no more than 1.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: true

Constraints

The number of nodes in the tree is in the range [0, 5000].
-10⁴ <= Node.val <= 10⁴

• Top-Down Depth-First Search
• Bottom-Up Depth-First Search

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: true

Constraints

The number of nodes in the tree is in the range [0, 5000].
-10⁴ <= Node.val <= 10⁴

Top-Down Depth-First Search

Intuition We can recursively check if every node in the tree is balanced. A node is balanced if the height difference between its left and right subtrees is at most 1, and both its left and right subtrees are also balanced.

Steps

• Define a helper function height(node) that calculates the height of a tree rooted at node.
• In the main function isBalanced(node):
  • If the node is null, return true (an empty tree is balanced).
  • Calculate the height of the left and right subtrees.
  • If the absolute difference between these heights is greater than 1, return false.
  • Recursively check if the left subtree is balanced.
  • Recursively check if the right subtree is balanced.
  • Return true only if all the above conditions are met.

class Solution:
    def height(self, root):
        if not root:
            return 0
        return 1 + max(self.height(root.left), self.height(root.right))

    def isBalanced(self, root):
        if not root:
            return True
        left_h = self.height(root.left)
        right_h = self.height(root.right)
        return abs(left_h - right_h) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

Complexity

• Time: O(n log n) in the best case (balanced tree), O(n²) in the worst case (skewed tree) because we recalculate heights for subtrees repeatedly.
• Space: O(n) for the recursion stack in the worst case.
• Notes: Simple to implement but inefficient for skewed trees as it computes the height of the same nodes multiple times.

Bottom-Up Depth-First Search

Intuition Instead of calculating height separately, we can check the balance condition while calculating the height from the bottom up. If any subtree is found to be unbalanced, we immediately propagate a failure signal (e.g., -1) up the recursion stack, avoiding further unnecessary calculations.

Steps

• Define a helper function checkHeight(node) that returns the height of the tree if it is balanced, or -1 if it is not balanced.
• In checkHeight(node):
  • If the node is null, return 0.
  • Recursively check the height of the left subtree. If it returns -1, propagate -1 immediately.
  • Recursively check the height of the right subtree. If it returns -1, propagate -1 immediately.
  • If the absolute difference between left and right heights is greater than 1, return -1.
  • Otherwise, return max(left_height, right_height) + 1.
• In the main function isBalanced(root), simply return checkHeight(root) != -1.

class Solution:
    def checkHeight(self, root):
        if not root:
            return 0
        left_h = self.checkHeight(root.left)
        if left_h == -1:
            return -1
        right_h = self.checkHeight(root.right)
        if right_h == -1:
            return -1
        if abs(left_h - right_h) > 1:
            return -1
        return 1 + max(left_h, right_h)

    def isBalanced(self, root):
        return self.checkHeight(root) != -1

Complexity

• Time: O(n) as we visit each node exactly once.
• Space: O(n) for the recursion stack in the worst case.
• Notes: This is the optimal approach as it prunes the recursion tree as soon as an imbalance is found.