110. Balanced Binary Tree (Easy)

Problem

Given a binary tree, determine if it is height-balanced: for every node, the left and right subtree heights differ by at most 1.

Example

• root = [3,9,20,null,null,15,7] → true
• root = [1,2,2,3,3,null,null,4,4] → false
• root = [] → true

LeetCode 110 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Top-down recompute heights at each node

For each node, compute heights of both subtrees, compare, then recurse.

Python

def is_balanced(root):
    def height(node):
        if not node:
            return 0
        return 1 + max(height(node.left), height(node.right))  # L1: O(n) subtree walk

    if not root:
        return True
    if abs(height(root.left) - height(root.right)) > 1:  # L2: O(n) height checks
        return False
    return is_balanced(root.left) and is_balanced(root.right)  # L3: recurse children

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function isBalanced(root: TreeNode | null): boolean {
    function height(node: TreeNode | null): number {
        if (!node) return 0;
        return 1 + Math.max(height(node.left), height(node.right));  // L1: O(n) subtree walk
    }
    if (!root) return true;
    if (Math.abs(height(root.left) - height(root.right)) > 1) return false;  // L2: O(n) height checks
    return isBalanced(root.left) && isBalanced(root.right);                   // L3: recurse children
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }
    l := height(node.Left)
    r := height(node.Right)
    if l > r {
        return 1 + l                              // L1: O(n) subtree walk
    }
    return 1 + r
}

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    l, r := height(root.Left), height(root.Right)
    diff := l - r
    if diff < -1 || diff > 1 {
        return false                              // L2: O(n) height checks
    }
    return isBalanced(root.Left) && isBalanced(root.Right)  // L3: recurse children
}

Swift

final class Solution { func isBalanced(_ root: TreeNode?) -> Bool { guard let root else { return true }; return abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right) }; private func height(_ node: TreeNode?) -> Int { guard let node else { return 0 }; return 1 + max(height(node.left), height(node.right)) } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1 (height walk)	$O(n)$	n nodes	$O(n²)$ ← dominates
L2 (abs check)	$O(1)$	n	$O(n)$
L3 (recurse children)	$O(1)$ dispatch	n	$O(n)$

For each of the n nodes, height walks the entire subtree beneath it. In a balanced tree of depth log n, the total work is $O(n log n)$; in a skewed tree, it’s $O(n²)$.

Complexity

• Time: $O(n²)$ worst case (skewed tree), driven by L1 re-walking subtrees.
• Space: $O(h)$ recursion.

Redundant work: we re-walk every subtree many times.

Approach 2: Bottom-up DFS with -1 sentinel (optimal)

Return the height of each subtree, or -1 if it’s already unbalanced. A node returns -1 if either child did.

Python

def is_balanced(root):
    def height(node):
        if not node:
            return 0
        lh = height(node.left)            # L1: recurse left
        if lh == -1:
            return -1                     # L2: propagate failure up
        rh = height(node.right)           # L3: recurse right
        if rh == -1:
            return -1                     # L4: propagate failure up
        if abs(lh - rh) > 1:
            return -1                     # L5: O(1) balance check
        return 1 + max(lh, rh)           # L6: O(1) return height

    return height(root) != -1

TypeScript

function isBalanced(root: TreeNode | null): boolean {
    function height(node: TreeNode | null): number {
        if (!node) return 0;
        const lh = height(node.left);            // L1: recurse left
        if (lh === -1) return -1;                // L2: propagate failure up
        const rh = height(node.right);           // L3: recurse right
        if (rh === -1) return -1;                // L4: propagate failure up
        if (Math.abs(lh - rh) > 1) return -1;   // L5: O(1) balance check
        return 1 + Math.max(lh, rh);            // L6: O(1) return height
    }
    return height(root) !== -1;
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func heightCheck(node *TreeNode) int {
    if node == nil {
        return 0
    }
    lh := heightCheck(node.Left)               // L1: recurse left
    if lh == -1 {
        return -1                              // L2: propagate failure up
    }
    rh := heightCheck(node.Right)              // L3: recurse right
    if rh == -1 {
        return -1                              // L4: propagate failure up
    }
    diff := lh - rh
    if diff < -1 || diff > 1 {
        return -1                              // L5: O(1) balance check
    }
    if lh > rh {
        return 1 + lh                          // L6: O(1) return height
    }
    return 1 + rh
}

func isBalanced(root *TreeNode) bool {
    return heightCheck(root) != -1
}

Swift

final class Solution { func isBalanced(_ root: TreeNode?) -> Bool { height(root) != -1 }; private func height(_ node: TreeNode?) -> Int { guard let node else { return 0 }; let left = height(node.left); if left == -1 { return -1 }; let right = height(node.right); if right == -1 || abs(left - right) > 1 { return -1 }; return 1 + max(left, right) } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1/L3 (recurse)	$O(1)$ dispatch	n	$O(n)$
L2/L4 (sentinel check)	$O(1)$	n	$O(n)$
L5 (balance check)	$O(1)$	n	$O(n)$
L6 (return height)	$O(1)$	n	$O(n)$ ← dominates (all lines tie)

Each node is visited exactly once. The -1 sentinel short-circuits traversal of subtrees that are already known to be unbalanced.

Complexity

• Time: $O(n)$. Each node visited once, driven by L1/L3.
• Space: $O(h)$ recursion.

Pattern

This is the “sentinel value” version of the diameter pattern: we want a single value back from the DFS, but we also need to propagate a failure condition. -1 is a legal “never going to match” sentinel because valid heights are ≥ 0.

An alternative is to return a tuple (balanced: bool, height: int), same complexity, marginally more code, but perhaps cleaner for larger invariant checks.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Top-down height per node	$O(n²)$	$O(h)$
Bottom-up with sentinel	$O(n)$	$O(h)$

The bottom-up form is the canonical fix for any “top-down recomputation” tree antipattern.

Test cases

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def is_balanced(root):
    def height(node):
        if not node:
            return 0
        lh = height(node.left)
        if lh == -1:
            return -1
        rh = height(node.right)
        if rh == -1:
            return -1
        if abs(lh - rh) > 1:
            return -1
        return 1 + max(lh, rh)
    return height(root) != -1

def _run_tests():
    assert is_balanced(build_tree([3, 9, 20, None, None, 15, 7])) == True
    assert is_balanced(build_tree([1, 2, 2, 3, 3, None, None, 4, 4])) == False
    assert is_balanced(None) == True
    assert is_balanced(build_tree([1])) == True
    # skewed tree of depth 4: not balanced
    t = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
    assert is_balanced(t) == False
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function isBalanced(root: TreeNode | null): boolean {
    function height(node: TreeNode | null): number {
        if (!node) return 0;
        const lh = height(node.left);
        if (lh === -1) return -1;
        const rh = height(node.right);
        if (rh === -1) return -1;
        if (Math.abs(lh - rh) > 1) return -1;
        return 1 + Math.max(lh, rh);
    }
    return height(root) !== -1;
}

console.assert(isBalanced(buildTree([3, 9, 20, null, null, 15, 7])) === true);
console.assert(isBalanced(buildTree([1, 2, 2, 3, 3, null, null, 4, 4])) === false);
console.assert(isBalanced(null) === true);
console.assert(isBalanced(buildTree([1])) === true);
const t = new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(4))));
console.assert(isBalanced(t) === false);
console.log("all tests pass");

Related data structures

• Binary Trees & BSTs, height DFS with short-circuit sentinel

Related concepts

• Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.
• DFS, the depth first traversal habit of following one branch before returning.