Balanced Binary Tree
Balanced Binary Tree is LeetCode 110 (Easy). Given the root of a binary tree, return true if it is height-balanced.
- A binary tree is height-balanced when, for every node, the heights of its left and right subtrees differ by at most 1.
- The height of an empty subtree is 0; a single node has height 1.
- An empty tree is balanced.
- Up to 5,000 nodes, so recomputing heights from every node can reach about 12.5 million visits on a skewed tree; one pass is the goal.
- The number of nodes in the tree is in the range [0, 5000].
- -10⁴ <= Node.val <= 10⁴
Intuition
A balanced binary tree is one where no node is lopsided: at each node, the left and right subtree heights differ by at most 1.
The check at a node needs the heights of both children, and a height is only known once the whole subtree below has been seen. That points to post-order traversal: children first, then the node.
One recursive function can do both jobs by using a signal value: a special return value that means "stop". Heights are never negative, so -1 means "this subtree is unbalanced", and every ancestor passes it straight up.
Any tree property that depends on both subtrees' results (height, diameter, sums, "is it valid below") is a post-order problem: compute children, combine at the node, return one value upward. When the answer is a yes/no and the parent needs a number, fold both into one return value with a sentinel such as -1.
Approach
Before reading on: write height(node) recursively. Then think about calling it from every node to compare the two sides. How many times is a node near the bottom visited? Can one function return the height and the balance verdict together?
Two ways to solve it
One post-order pass returns each subtree's height, or -1 as soon as any node is lopsided.
- Speed: every node is visited once.
- Early exit: a -1 skips the rest of the tree.
- Space: only the recursion stack.
The answer interviewers look for.
At each node, measure both subtree heights with a separate depth, compare, then recurse into both children.
- Simple: follows the definition word for word.
- Cost: a node is measured once per ancestor.
- Typical: O(n log n) on bushy trees, O(n²) on chains.
Correct, but it repeats work.
Returning heights upward means no subtree is measured twice, so the bottom-up pass is linear even on a chain. The steps, code and live demo below follow it, and the top-down code is further down.
Define height(node) with a sentinel
It returns the subtree's height if that subtree is balanced, and -1 if it is not. An empty subtree returns 0. One function returning a height or -1 does both jobs in a single walk of the tree.
Recurse left, and stop early on -1
If the left subtree is already unbalanced, return -1 without visiting the right subtree. Once one subtree is unbalanced the whole tree is, so the rest of the work can be skipped.
Recurse right, then compare
This node is unbalanced, so return -1, when either:
- the right subtree returned -1, or
- the two heights differ by more than 1.
Each node is checked using its children's real heights, which post-order has just computed.
Report this node's height
Otherwise return 1 + max(left, right) so the parent can run the same comparison.
Answer at the root
The tree is balanced exactly when height(root) is not -1. -1 can only reach the root if some node failed the check.
Balanced Binary Tree solution in Python | C++ | Java
height(root) != -1 is false.height(root) != -1 is false. The faded nodes were never visited: once one node fails, the rest cannot change the answer.Top-down height check
depth measures a subtree from scratch. isBalanced checks the root's two depths, then asks the same question of each child, exactly as the definition reads.
Common pitfalls
Checking only the root
return abs(depth(root.left) - depth(root.right)) <= 1
return height(root) != -1 # checks every node
In the third example both of the root's subtrees have height 3, so this returns true, yet each node 2 has subtrees of heights 2 and 0. The rule applies at every node.
Edge cases
Balanced only up to 2 nodes. With 3 nodes in a line, the top node has heights 2 and 0 and returns -1. The recursion goes as deep as the chain, up to 5,000 frames, which fits in C++ and Java default stacks; Python needs sys.setrecursionlimit above its default of 1,000.
Complexity
Balanced binary tree vs related ideas
"Balanced" is used for several different things, which is a common source of confusion.
| Term | Meaning | Where it appears |
|---|---|---|
| Height-balanced binary tree | at every node, subtree heights differ by ≤ 1 | LeetCode 110, AVL trees |
| Balanced binary search tree | a BST kept at O(log n) height by rotations | AVL, red-black trees, std::map, TreeMap |
| Complete binary tree | every level full except the last, filled from the left | binary heaps |
| Perfect binary tree | every level completely full | a special case of all of the above |
Balanced Binary Tree FAQ
How do you check if a binary tree is balanced?
- Rule: at every node, left and right subtree heights differ by at most 1.
- Method: one post-order DFS,
height(node), that returns the height or -1 if the subtree is unbalanced. - At each node: get left height (stop if -1), get right height, return -1 if right is -1 or
|left - right| > 1, else1 + max(left, right). - Answer:
height(root) != -1. - Complexity: O(n) time, O(h) space.
What is a height balanced binary tree?
A binary tree in which, for every node, the heights of the left and right subtrees differ by at most 1. This keeps the tree's height O(log n), which is why AVL trees enforce exactly this rule.
Is a balanced binary tree the same as a balanced binary search tree?
No. A balanced binary tree is only about shape. A balanced binary search tree must also keep the BST order (left < node < right) and usually restores balance with rotations after every insert or delete, as AVL and red-black trees do.