Balanced Binary Tree

Checking balance at a single node needs the heights of its two subtrees. The naive approach recomputes those heights from scratch for every node it checks; the optimal one computes each height only once, bailing out the instant an imbalance is found anywhere below.

Brute Force (recompute height per node)

Time O(n^2)Space O(h)

For every node, independently compute the height of its left and right subtree, and recurse into both children to check the rest of the tree.

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: TreeNode | None) -> bool:
        def height(node: TreeNode | None) -> int:
            if node is None:
                return 0
            return 1 + max(height(node.left), height(node.right))

        if root is None:
            return True
        if abs(height(root.left) - height(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

Complexity: height walks a whole subtree and is called from every node → O(n^2) worst case (a skewed tree of depth n triggers O(n) height calls each doing O(n) work). Recursion depth → O(h) space.

Bottom-Up with Early Exit

OptimalTime O(n)Space O(h)

Combine the height computation and the balance check into one post-order pass: return the real height when a subtree is balanced, or a sentinel -1 the moment an imbalance is found. Once -1 appears, it propagates straight up without doing any more work on siblings.

class Solution:
    def isBalanced(self, root: TreeNode | None) -> bool:
        def check(node: TreeNode | None) -> int:
            if node is None:
                return 0
            left = check(node.left)
            if left == -1:
                return -1
            right = check(node.right)
            if right == -1:
                return -1
            if abs(left - right) > 1:
                return -1
            return 1 + max(left, right)

        return check(root) != -1

Tracing root = [1,2,2,3,3,null,null,4,4] (using a/b suffixes to tell the two 2s and two 3s apart):

1 / 4

comparingseendiscarded

Leaves 4a and 4b return height 1 each.

Complexity: each node’s height is computed exactly once, in O(1) work beyond its children’s results → O(n) time. Space is still the recursion stack → O(h).