LogoKode$word

LeetCode 110: Balanced Binary Tree – Java Optimized DFS Solution Explained

Learn how to solve LeetCode 110 Balanced Binary Tree using optimized DFS and height calculation in Java. Includes brute force approach, optimized recursive solution, intuition, dry run, complexity analysis, interview explanation, and common mistakes.

Krishna Shrivastava
1 views
LinkedInGithubX
0
0
LeetCodeBalanced Binary TreeJavaBinary TreeDFSTree HeightRecursionTree
LeetCode 110: Balanced Binary Tree – Java Optimized DFS Solution Explained
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 110 – Balanced Binary Tree is one of the most important binary tree interview problems.

This problem teaches:

  1. Tree recursion
  2. Height calculation
  3. Depth First Search (DFS)
  4. Bottom-up recursion
  5. Optimization techniques

It is frequently asked in coding interviews because it checks whether you can:

  1. Traverse trees efficiently
  2. Avoid repeated calculations
  3. Combine recursion with conditions
  4. Optimize brute force tree solutions

This problem is also a foundation for advanced tree problems like:

  1. AVL Trees
  2. Height-balanced trees
  3. Diameter of Binary Tree
  4. Tree DP problems

Problem Link

🔗 https://leetcode.com/problems/balanced-binary-tree/

Problem Statement

Given the root of a binary tree:

Return:

true

if the tree is:

height-balanced

Otherwise return:

false

What is a Balanced Binary Tree?

A binary tree is balanced if:

For every node,
|height(left subtree) - height(right subtree)| <= 1

Meaning:

  1. Left and right subtree heights should not differ by more than:
1

Example 1

Input

root = [3,9,20,null,null,15,7]

Tree:

3
/ \
9 20
/ \
15 7

Output

true

Explanation:

Every node satisfies:

height difference <= 1

Example 2

Input

root = [1,2,2,3,3,null,null,4,4]

Tree:

1
/ \
2 2
/ \
3 3
/ \
4 4

Output

false

Explanation:

Left subtree becomes much deeper than right subtree.

Difference becomes greater than:

1

Key Observation

To determine if tree is balanced:

At every node we need:

  1. Height of left subtree
  2. Height of right subtree
  3. Compare difference

This naturally becomes a recursive DFS problem.

Brute Force Approach

Intuition

For every node:

  1. Calculate left height
  2. Calculate right height
  3. Compare difference
  4. Recursively check children

Brute Force Java Solution

class Solution {

public int height(TreeNode root) {

if(root == null)
return 0;

return 1 + Math.max(height(root.left), height(root.right));
}

public boolean isBalanced(TreeNode root) {

if(root == null)
return true;

int left = height(root.left);

int right = height(root.right);

if(Math.abs(left - right) > 1)
return false;

return isBalanced(root.left) && isBalanced(root.right);
}
}

Problem with Brute Force

The height function gets called repeatedly.

For every node:

  1. Heights are recalculated again and again.

This increases complexity significantly.

Brute Force Complexity

Time Complexity

O(N²)

because height calculation repeats.

Space Complexity

O(H)

for recursion stack.

Optimized DFS Approach

Instead of:

  1. Calculating heights separately

We can:

  1. Calculate height and balance together.

Core Optimization Idea

While calculating height:

If subtree becomes unbalanced:

Return negative value immediately

This avoids unnecessary computation.

Optimized Java Solution

class Solution {

public int solve(TreeNode roo) {

if(roo == null)
return 0;

int left = solve(roo.left);

if(left < 0) {
return -1;
}

int right = solve(roo.right);

if(right < 0) {
return -1;
}

if(Math.abs(left - right) > 1) {
return -1000;
}

return 1 + Math.max(left, right);
}

public boolean isBalanced(TreeNode root) {

int ans = solve(root);

return ans < 0 ? false : true;
}
}

Cleaner Optimized Version

We can simplify negative returns using:

-1

consistently.

Cleaner Java Solution

class Solution {

public int height(TreeNode root) {

if(root == null)
return 0;

int left = height(root.left);

if(left == -1)
return -1;

int right = height(root.right);

if(right == -1)
return -1;

if(Math.abs(left - right) > 1)
return -1;

return 1 + Math.max(left, right);
}

public boolean isBalanced(TreeNode root) {

return height(root) != -1;
}
}

Why This Works

At every node:

  1. Recursively calculate left height
  2. Recursively calculate right height
  3. If difference > 1:
Tree is unbalanced
  1. Propagate failure upward immediately.

Dry Run

Input

1
/ \
2 2
/ \
3 3
/ \
4 4

Step 1

Start from leaf nodes:

4 → height = 1

Step 2

Node:

3

gets:

left = 1
right = 1

Difference:

0

Balanced.

Height:

2

Step 3

At node:

2

Left height:

2

Right height:

0

Difference:

2

Unbalanced.

Return:

-1

Final Result

Tree is:

Not balanced

Return:

false

Time Complexity Analysis

Optimized DFS Solution

Time Complexity

O(N)

because every node is visited once.

Space Complexity

O(H)

where:

H = height of tree

Worst case:

O(N)

for skewed tree.

Brute Force vs Optimized

ApproachTime ComplexitySpace Complexity
Brute ForceO(N²)O(H)
Optimized DFSO(N)O(H)

Interview Explanation

In interviews, explain:

Instead of recalculating heights repeatedly, we combine height calculation and balance checking into a single DFS traversal.

This demonstrates:

  1. Optimization skills
  2. Recursive DFS understanding
  3. Bottom-up tree processing

Common Mistakes

1. Recalculating Heights Repeatedly

This causes:

O(N²)

complexity.

2. Forgetting Absolute Difference

Always use:

Math.abs(left - right)

3. Not Handling Null Nodes

Base case:

if(root == null)
return 0;

is necessary.

FAQs

Q1. What is a balanced binary tree?

A tree where left and right subtree heights differ by at most:

1

for every node.

Q2. Why use DFS?

Because height calculation naturally follows recursive depth traversal.

Q3. Why return -1?

It acts as a signal:

Subtree already unbalanced

Q4. Is this problem important for interviews?

Very important.

It is one of the most common tree optimization questions.

Conclusion

LeetCode 110 is an excellent binary tree optimization problem.

It teaches:

  1. DFS traversal
  2. Height calculation
  3. Bottom-up recursion
  4. Optimization techniques

The key insight is:

Combine balance checking and height calculation in one DFS traversal.

Once you understand this optimization pattern, many advanced tree problems become much easier.

Related Articles

LeetCode 104: Maximum Depth of Binary Tree – Java Recursive Solution Explained

LeetCode 104: Maximum Depth of Binary Tree – Java Recursive Solution Explained

Learn how to solve LeetCode 104 Maximum Depth of Binary Tree using recursion and DFS in Java. Includes brute force intuition, optimized recursive approach, BFS solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 543: Diameter of Binary Tree – Java DFS Solution Explained

LeetCode 543: Diameter of Binary Tree – Java DFS Solution Explained

Learn how to solve LeetCode 543 Diameter of Binary Tree using optimized DFS recursion in Java. Includes brute force approach, optimized solution, intuition, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 144 Binary Tree Preorder Traversal using Recursive and Iterative approaches in Java. Includes traversal intuition, stack-based solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Recursion in Java - Complete Guide With Examples and Practice Problems

Recursion in Java - Complete Guide With Examples and Practice Problems

Learn recursion in Java from scratch. Includes how recursion works, base case, recursive case, types of recursion, dry runs, time & space complexity, and top LeetCode problems with solutions.

Read Article
Ai Assistant Kas