EasyTreeDepth-First SearchBinary Tree

Balanced Binary Tree

1 approach, code in every language

You are given the root of a binary tree. The tree is height-balanced when, for every node, the heights of its left and right subtrees differ by no more than one.

Return true if the whole tree is height-balanced, and false otherwise.

Example 1

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

Output: true

Every node's two subtrees differ in height by at most 1.

Example 2

Input: root = [1,2,2,3,3,null,null,4,4]

Output: false

The left subtree is much deeper than the right, so the root fails the balance condition.

Constraints

The number of nodes in the tree is in the range [0, 5000].
-10^4 <= Node.val <= 10^4

Bottom-Up Height with -1 Sentinel

Compute heights post-order and short-circuit by returning -1 the moment any subtree is found unbalanced.

Loading animation…

Intuition

A naive solution recomputes the height of every subtree while separately checking balance, which repeats work and drifts toward O(n log n) or worse. Instead, we fold the balance test into the height computation: a single post-order function returns the height of a balanced subtree, or a sentinel value of -1 if imbalance was detected anywhere below. Because a child already reports -1 when it is unbalanced, the parent can bail out immediately without finishing its work. This propagation means the answer for the entire tree is decided in one linear sweep. If the root call returns anything other than -1, the tree is balanced.

Algorithm walkthrough

1Define check(node) returning the subtree height, or -1 if the subtree is unbalanced.
2A null node has height 0.
3Recurse left; if it returns -1, immediately propagate -1 upward.
4Recurse right; if it returns -1, propagate -1 as well.
5If |leftHeight - rightHeight| > 1 return -1, otherwise return 1 + max(leftHeight, rightHeight).
6The tree is balanced exactly when check(root) is not -1.

Implementation

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(node):
            if not node:
                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

Time

O(n)

Space

O(h)

Each node is visited once; the recursion stack uses O(h) space, which is O(log n) when balanced and O(n) in the worst case.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Scaffold Stands Steady is our own problem on the technique behind Balanced Binary Tree: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free