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

Watch the post-order pass on root = [1,2,2,3,3,null,null,4,4] (the a/b suffixes tell the duplicate values apart): each box accumulates the height its subtree returns, and the sentinel -1 appears the instant two subtree heights differ by more than one.

1·

2a·

2b·

3a·

3b·

4a·

4b·

boxes show each node value plus its returned height

current call

node—

left—

right—

returns—

isBalanced?

1 / 9

computed height

currentcomparingdiscarded

Post-order pass: a node decides only after its children report heights. Every call returns a real height, or the sentinel -1 the moment an imbalance appears below it.

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

Balanced Binary Tree

Brute Force (recompute height per node)

Bottom-Up with Early Exit

More Trees practice