Balanced Binary Tree solution and explanation
Google
9 more videos on this problem
Balanced Binary Tree - Leetcode 110 - PythonNeetCode · 13:11 · 393K views
Balanced Binary Tree - Leetcode 110 - Trees (Python)Greg Hogg · 6:06 · 23K views
LeetCode 110 | Balanced Binary Tree | Solution Explained (Java + Whiteboard)Xavier Elon · 11:30 · 8K views
[Java] Leetcode 110. Balanced Binary Tree [Binary Tree #15]Eric Programming · 8:31 · 4K views
110. Balanced Binary Tree Java SolutionCode with Carter · 9:40 · 3K views
Balanced Binary Tree | Minimum Depth of a Binary Tree | LeetCode Java | GeekificGeekific · 4:50 · 857 views
LeetCode 110 - Balanced Binary Tree - C++iamdriy · 9:59 · 808 views
Leetcode 110: Balanced Binary Tree | Master Trees | Intuition and ApproachCode Concepts with Animesh · 4:13 · 761 views
Balanced Binary Tree - Leetcode 110 - JavaMastering Programming · 7:23 · 692 views
Balanced Binary Tree | LeetCode 110 (Easy)Destination FAANG · 8:43 · 483 views
The problem
Given a binary tree, determine if it is height-balanced.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4] Output: false
Example 3:
Input: root = [] Output: true
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]. -104 <= Node.val <= 104
Approach overview
Problem Overview: You are given the root of a binary tree and must determine whether it is height-balanced. A binary tree is balanced when the height difference between the left and right subtree of every node is at most one.
Approach 1: Recursive Height Calculation (O(n^2) time, O(h) space)
This straightforward solution computes the height of the left and right subtree for every node, then checks whether the difference exceeds one. Use a recursive height(node) function that returns 1 + max(leftHeight, rightHeight). During traversal, repeatedly call this function while verifying the balance condition. The drawback is repeated work: the height of the same subtree may be recomputed multiple times. In the worst case (a skewed tree), this leads to O(n^2) time while the recursion stack uses O(h) space where h is the tree height.
Approach 2: Optimized Recursive Approach (O(n) time, O(h) space)
This method combines balance checking and height calculation in a single DFS traversal. Instead of computing subtree heights separately, the recursive function returns the height of the subtree while also detecting imbalance early. If a subtree is already unbalanced, return a sentinel value such as -1. Each parent node checks whether either child returned -1 or whether the height difference exceeds one. If so, propagate -1 upward. Otherwise return the computed height. Because each node is visited exactly once, the algorithm runs in O(n) time with O(h) recursion stack space.
The solution relies on a depth-first traversal pattern commonly used in tree problems. Specifically, it performs a post-order DFS so the algorithm processes child subtrees before evaluating the parent node. This pattern appears frequently in depth-first search problems involving structural checks or subtree properties.
Balanced tree checks are a fundamental concept in binary tree algorithms because many data structures (AVL trees, Red-Black trees) rely on height balance to maintain efficient operations. Practicing this problem helps build intuition for computing subtree properties during traversal.
Recommended for interviews: The optimized recursive approach is the expected solution. It demonstrates that you can avoid redundant computations by combining height calculation with the balance check in a single DFS. Mentioning the naive O(n^2) approach first shows you understand the baseline, while implementing the O(n) solution proves you can optimize recursive tree algorithms.
Approach 1: Recursive Height Calculation
This approach involves recursively calculating the height of each subtree and checking if the subtrees are balanced by ensuring the difference in height is not more than one.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
def height(node):
if not node:
return 0
return max(height(node.left), height(node.right)) + 1
left_height = height(root.left)
right_height = height(root.right)
if abs(left_height - right_height) > 1:
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BalancedBinaryTree {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int height(TreeNode node) {
if (node == null) return 0;
return Math.max(height(node.left), height(node.right)) + 1;
}
}#include <iostream>
#include <cmath>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int height(TreeNode* node) {
if (!node) return 0;
return max(height(node->left), height(node->right)) + 1;
}
bool isBalanced(TreeNode* root) {
if (!root) return true;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (abs(leftHeight - rightHeight) > 1) return false;
return isBalanced(root->left) && isBalanced(root->right);
}function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function isBalanced(root) {
if (root === null) return true;
function height(node) {
if (node === null) return 0;
return Math.max(height(node.left), height(node.right)) + 1;
}
const leftHeight = height(root.left);
const rightHeight = height(root.right);
return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int height(struct TreeNode* node) {
if (node == NULL) return 0;
int leftHeight = height(node->left);
int rightHeight = height(node->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool isBalanced(struct TreeNode* root) {
if (root == NULL) return true;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return abs(leftHeight - rightHeight) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool IsBalanced(TreeNode root) {
if (root == null) return true;
int leftHeight = Height(root.left);
int rightHeight = Height(root.right);
return Math.Abs(leftHeight - rightHeight) <= 1 && IsBalanced(root.left) && IsBalanced(root.right);
}
private int Height(TreeNode node) {
if (node == null) return 0;
return Math.Max(Height(node.left), Height(node.right)) + 1;
}
}This Python implementation utilizes a nested helper function height to calculate the height of each node’s subtrees. The primary function isBalanced checks if the balance criteria are satisfied recursively.
Time Complexity: O(N^2), due to redundant height recalculations. Space Complexity: O(N) because of the recursion depth.
Approach 2: Optimized Recursive Approach
This optimized approach calculates the height and balance status of a tree in a single recursive function, thus avoiding recalculations by returning both height and balanced status in form of tuples or objects.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def check_balance(node):
if not node:
return (0, True) # height, is_balanced
left_height, left_balanced = check_balance(node.left)
if not left_balanced:
return (0, False)
right_height, right_balanced = check_balance(node.right)
if not right_balanced:
return (0, False)
balanced = abs(left_height - right_height) <= 1
return (max(left_height, right_height) + 1, balanced)
return check_balance(root)[1]class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BalancedBinaryTree {
public boolean isBalanced(TreeNode root) {
return checkBalance(root).balanced;
}
private class Result {
int height;
boolean balanced;
Result(int height, boolean balanced) {
this.height = height;
this.balanced = balanced;
}
}
private Result checkBalance(TreeNode node) {
if (node == null) return new Result(0, true);
Result left = checkBalance(node.left);
if (!left.balanced) return new Result(0, false);
Result right = checkBalance(node.right);
if (!right.balanced) return new Result(0, false);
boolean balanced = Math.abs(left.height - right.height) <= 1;
return new Result(Math.max(left.height, right.height) + 1, balanced);
}
}#include <iostream>
#include <cmath>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool isBalanced(TreeNode* root) {
return checkBalance(root).second;
}
private:
pair<int, bool> checkBalance(TreeNode* node) {
if (!node) return {0, true};
auto left = checkBalance(node->left);
if (!left.second) return {0, false};
auto right = checkBalance(node->right);
if (!right.second) return {0, false};
bool balanced = abs(left.first - right.first) <= 1;
return {fmax(left.first, right.first) + 1, balanced};
}
};function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function isBalanced(root) {
function checkBalance(node) {
if (node === null) return { height: 0, balanced: true };
const left = checkBalance(node.left);
if (!left.balanced) return { height: 0, balanced: false };
const right = checkBalance(node.right);
if (!right.balanced) return { height: 0, balanced: false };
const balanced = Math.abs(left.height - right.height) <= 1;
return { height: Math.max(left.height, right.height) + 1, balanced: balanced };
}
return checkBalance(root).balanced;
}#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct Result {
int height;
bool balanced;
};
struct Result checkBalance(struct TreeNode* node) {
if (!node) return (struct Result){0, true};
struct Result left = checkBalance(node->left);
if (!left.balanced) return (struct Result){0, false};
struct Result right = checkBalance(node->right);
if (!right.balanced) return (struct Result){0, false};
bool balanced = abs(left.height - right.height) <= 1;
return (struct Result){fmax(left.height, right.height) + 1, balanced};
}
bool isBalanced(struct TreeNode* root) {
return checkBalance(root).balanced;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool IsBalanced(TreeNode root) {
return CheckBalance(root).balanced;
}
private (int height, bool balanced) CheckBalance(TreeNode node) {
if (node == null) return (0, true);
var left = CheckBalance(node.left);
if (!left.balanced) return (0, false);
var right = CheckBalance(node.right);
if (!right.balanced) return (0, false);
bool balanced = Math.Abs(left.height - right.height) <= 1;
return (Math.Max(left.height, right.height) + 1, balanced);
}
}This Python solution defines a more efficient check_balance function, returning a tuple comprising the current node's height and balance situation, halting further recursion when imbalance is found.
Time Complexity: O(N). Space Complexity: O(N) for recursion stack.
Approach 3: Bottom-Up Recursion
We define a function height(root) to calculate the height of a binary tree, with the following logic:
- If the binary tree
rootis null, return0. - Otherwise, recursively calculate the heights of the left and right subtrees, denoted as
landrrespectively. If eitherlorris-1, or the absolute difference betweenlandris greater than1, then return-1. Otherwise, returnmax(l, r) + 1.
Therefore, if the function height(root) returns -1, it means the binary tree root is not balanced. Otherwise, it is balanced.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isBalanced(root: TreeNode | null): boolean {
const dfs = (root: TreeNode | null) => {
if (root == null) {
return 0;
}
const left = dfs(root.left);
const right = dfs(root.right);
if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
return -1;
}
return 1 + Math.max(left, right);
};
return dfs(root) > -1;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
var height func(*TreeNode) int
height = func(root *TreeNode) int {
if root == nil {
return 0
}
l, r := height(root.Left), height(root.Right)
if l == -1 || r == -1 || abs(l-r) > 1 {
return -1
}
if l > r {
return 1 + l
}
return 1 + r
}
return height(root) >= 0
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
Self::dfs(&root) > -1
}
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
if root.is_none() {
return 0;
}
let node = root.as_ref().unwrap().borrow();
let left = Self::dfs(&node.left);
let right = Self::dfs(&node.right);
if left == -1 || right == -1 || (left - right).abs() > 1 {
return -1;
}
1 + left.max(right)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Height Calculation | Time Complexity: O(N^2), due to redundant height recalculations. Space Complexity: O(N) because of the recursion depth. |
| Optimized Recursive Approach | Time Complexity: O(N). Space Complexity: O(N) for recursion stack. |
| Bottom-Up Recursion | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Height Calculation | O(n^2) | O(h) | Simple baseline approach when learning recursion on trees |
| Optimized Recursive DFS (Post-order) | O(n) | O(h) | Preferred interview solution that avoids repeated height calculations |
Frequently asked questions
Is Balanced Binary Tree easy or hard?
Balanced Binary Tree is categorized as an Easy problem on LeetCode. The challenge lies in recognizing that height calculation and balance checking should be combined into one DFS traversal to achieve the optimal O(n) solution.
How to solve Balanced Binary Tree in O(n)?
Use a post-order DFS that returns the height of each subtree while checking the balance condition. If a subtree is unbalanced, return a sentinel value such as -1 and propagate it upward. This avoids repeated height calculations and ensures every node is processed only once.
What is the best approach for Balanced Binary Tree?
The optimized recursive depth-first search approach is the best solution. It calculates subtree height and checks balance in the same traversal using post-order DFS. Each node is visited once, resulting in O(n) time complexity and O(h) space for the recursion stack.
What data structure is used in Balanced Binary Tree?
The problem uses a binary tree data structure. The algorithm typically relies on depth-first search recursion to compute subtree heights and verify the balance condition at every node.
What is the time complexity of Balanced Binary Tree?
The optimal algorithm runs in O(n) time because each node in the binary tree is visited exactly once during the DFS traversal. A naive approach that recomputes subtree heights at every node takes O(n^2) time in the worst case.
Balanced Binary Tree Python or Java solution approach?
Most Python and Java solutions implement a recursive DFS helper function that returns subtree height. If the height difference exceeds one, the function returns -1 to indicate imbalance. The main function checks whether the final result is -1 to determine if the tree is balanced.
Is Balanced Binary Tree asked at Google, Amazon, or Meta?
Balanced Binary Tree is a common interview problem at companies like Amazon, Google, and Meta because it tests recursion, tree traversal, and understanding of subtree properties. Variations of this problem also appear in system design discussions involving balanced tree structures.