110. Balanced Binary Tree

[#binary-tree]

## description

## 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

Example 1:

plain text

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

Example 2:

plain text

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

Example 3:

plain text

Input: root = []
Output: true

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

Constraints:

## notes

### Intuition

A tree is balanced if the depth difference between left and right subtrees never exceeds 1 at any node. We can combine the balance check with height calculation by using a sentinel value (-1) to propagate imbalance upward.

### Implementation

Use a recursive DFS function that returns the height of a subtree, or -1 if it's unbalanced. Base case: null node returns 0. Recurse on the left subtree—if it returns -1, immediately propagate -1 upward. Do the same for the right subtree. If both subtrees are balanced, check if their height difference exceeds 1; if so, return -1. Otherwise, return 1 + max(left, right). In the main function, the tree is balanced if DFS doesn't return -1.

### Edge-cases

An empty tree is considered balanced (returns height 0).

–
Time: O(n) — visit each node once
–
Space: O(h) — recursion stack depth equals tree height

### Complexity

## solution

python

from typing import Optional
from lcutils import TreeNode

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(root: Optional[TreeNode]) -> int:
            if not root:
                return 0
            
            lh = height(root.left)
            if lh == -1:
                return -1
            
            rh = height(root.right)
            if rh == -1:
                return -1
            
            if abs(lh - rh) > 1:
                return -1
            
            return 1 + max(lh, rh)

        return height(root) != -1
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()

--EOF--