Balanced Binary Tree — Solution in Python, Java & C++
Balanced Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Balanced Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Google, Microsoft and Bloomberg interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Microsoft, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return true if it is height-balanced and false otherwise.
A tree is height-balanced when, at every node, the heights of the left and right subtrees differ by at most one. The height of an empty subtree is 0.
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: true
Explanation: At the root the subtrees have heights 1 and 2; every other node is also within one.
Example 2
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: At the root the left subtree has height 3 and the right one height 1.
Example 3
Input: root = []
Output: true
Constraints
The number of nodes in the tree is in the range [0, 5000]-10^4 <= Node.val <= 10^4
Hints for Balanced Binary Tree
Hint 1
Checking the root alone is not enough — the condition must hold at every node.
Hint 2
Calling a height function at every node works but recomputes heights over and over: O(n^2) on a chain.
Hint 3
Compute heights bottom-up and let the helper return a sentinel such as -1 as soon as any subtree is unbalanced.
How to solve Balanced Binary Tree
One post-order walk can compute every subtree's height and check balance at the same time: a helper returns a node's height, or -1 if anything below it is already unbalanced, and the -1 propagates straight up.
Approach
check(null) = 0.- For a node, compute
l = check(left); if it is -1 return -1. Do the same forr. - If
|l - r| > 1return -1. - Otherwise return
1 + max(l, r). - The tree is balanced when
check(root) != -1.
Why it works
Every node's balance condition is tested exactly when both of its subtree heights are known, so every node is checked, and a single failure anywhere forces -1 all the way to the root. Heights are each computed once, instead of once per ancestor.
Complexity
- Time —
O(n) - Space —
O(h) recursion depth
Pitfalls
- Comparing only the root's two subtree heights accepts trees like
[1,2,2,3,null,null,3,4,null,null,4]that are unbalanced lower down. - The top-down version (height at every node) is O(n^2) on skewed trees.
- An empty tree is balanced.
Reference solution
Python
from typing import Optional
def isBalanced(root: Optional[TreeNode]) -> bool:
def check(node):
if node is None:
return 0
l = check(node.left)
if l < 0:
return -1
r = check(node.right)
if r < 0 or abs(l - r) > 1:
return -1
return 1 + max(l, r)
return check(root) >= 0Java
public static boolean isBalanced(TreeNode root) {
return balancedHeight(root) >= 0;
}
static int balancedHeight(TreeNode node) {
if (node == null) return 0;
int l = balancedHeight(node.left);
if (l < 0) return -1;
int r = balancedHeight(node.right);
if (r < 0 || Math.abs(l - r) > 1) return -1;
return 1 + Math.max(l, r);
}C++
int balancedHeight(TreeNode* node) {
if (!node) return 0;
int l = balancedHeight(node->left);
if (l < 0) return -1;
int r = balancedHeight(node->right);
if (r < 0 || abs(l - r) > 1) return -1;
return 1 + max(l, r);
}
bool isBalanced(TreeNode* root) {
return balancedHeight(root) >= 0;
}JavaScript
var isBalanced = function(root) {
return balancedHeight(root) >= 0;
};
var balancedHeight = function(node) {
if (node === null) return 0;
var l = balancedHeight(node.left);
if (l < 0) return -1;
var r = balancedHeight(node.right);
if (r < 0 || Math.abs(l - r) > 1) return -1;
return 1 + Math.max(l, r);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals