Leetcode - 110. Balanced Binary Tree

Easy

Jan 02, 2026

#binary-tree

110. Balanced Binary Tree

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

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

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

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()