EASY

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced: for every node, the height difference between its left and right subtrees is at most 1.

Example

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

Output true

Key Pointers

Checking height and balance separately at every node costs O(n²) in the worst case — fold both into one bottom-up pass instead.
A common trick: have the height helper return -1 the moment it detects an imbalance, and let that -1 propagate straight up without further work.
One unbalanced subtree makes the whole tree unbalanced, so short-circuiting on the first -1 is safe.

Step-by-Step Analysis

Define height(node); base case None returns 0.
Recursively compute the left height; if it's -1, return -1 immediately.
Recursively compute the right height; if it's -1, return -1 immediately.
If abs(left - right) > 1, return -1; otherwise return 1 + max(left, right).
The tree is balanced iff height(root) != -1.

Complexity

Time: O(n) — Space: O(h)

Code

def isBalanced(root: TreeNode | None) -> bool:
    def height(node: TreeNode | None) -> int:
        if not node:
            return 0
        left = height(node.left)
        if left == -1:
            return -1
        right = height(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return height(root) != -1

Code Explanation

How the solution above works, piece by piece.

height returns the subtree height, or −1 as a special value meaning "unbalanced somewhere below".
Compute the left height; if it's −1, stop immediately and pass −1 up. Same for the right.
If the two heights differ by more than 1, this node is unbalanced: return −1.
Otherwise return the normal height 1 + max(left, right).
Checking and measuring in the same pass makes it O(n); calling a separate height function at every node would be O(n²).

Visual Walkthrough

Running it on root = [3, 9, 20, null, null, 15, 7]:

Each node compares its two children's heights. A difference above 1 anywhere would return −1, which the code uses as an "unbalanced" signal that is passed straight up without further work.

Video Explanation

NeetCode — Balanced Binary Tree, LeetCode 110