Back to Trees
Easy
Balanced Binary Tree
Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Examples
Input:root = [3,9,20,null,null,15,7]
Output:true
Input:root = [1,2,2,3,3,null,null,4,4]
Output:false
Constraints
The number of nodes in the tree is in the range [0, 5000].-10^4 <= Node.val <= 10^4
Approach
For every node, calculate the height of its left and right subtrees. If the difference is greater than 1, return false. Otherwise, recursively check if the left and right subtrees are also balanced. This recalculates heights multiple times.
Complexity Analysis
Time Complexity
O(n^2)
Space Complexity
O(h)
This approach is inefficient because `height` is called repeatedly for the same nodes.
Solution.java
class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; int leftHeight = height(root.left); int rightHeight = height(root.right); if (Math.abs(leftHeight - rightHeight) > 1) { return false; } return isBalanced(root.left) && isBalanced(root.right); } private int height(TreeNode root) { if (root == null) return 0; return 1 + Math.max(height(root.left), height(root.right)); }}