mediumDSA

How do you check if a binary tree is balanced?

Q: How do you check if a binary tree is balanced?

**Intuition.** A tree is height-balanced if, at **every** node, the heights of the left and right subtrees differ by at most 1. The naive check recomputes heights repeatedly (O(n²)). The trick: compute height **bottom-up** and use a sentinel (-1) to signal "already unbalanced", so the whole check is a single O(n) pass. |height(left) − height(right)| ≤ 1 at every node balanced ✓ <line x1="130" y1="58" x2="165" y2="100" stroke="currentColor"

1.1k views

Understand the problem

Explain balance checking.

treesbalanced

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Bottom-up balance check

Run Playground

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

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


# --- demo ---
balanced = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
skewed = TreeNode(1, TreeNode(2, TreeNode(3)))   # 1->2->3 chain
print(is_balanced(balanced))   # True
print(is_balanced(skewed))     # False

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you implement a queue using two stacks?

How do you check if a graph is bipartite?