Why Check if Binary Tree is Balanced in DSA Java?

The Big Idea

What if you could instantly know if your tree is balanced without counting every branch?

The Scenario

Imagine you have a family tree drawn on paper. You want to quickly see if the tree is balanced, meaning no side is too heavy or too light compared to the other. Doing this by eye is hard and confusing when the tree is big.

The Problem

Manually checking each branch's height and comparing takes a lot of time and mistakes happen easily. You might miss a branch or miscount levels, leading to wrong conclusions about balance.

The Solution

Using a program to check balance automatically looks at each branch's height and ensures the difference is never more than one. This saves time and avoids errors, giving a clear yes or no answer quickly.

Before vs After

✗ Before

int height(Node node) {
  if (node == null) return 0;
  int leftHeight = height(node.left);
  int rightHeight = height(node.right);
  return Math.max(leftHeight, rightHeight) + 1;
}

boolean isBalanced(Node node) {
  if (node == null) return true;
  int leftHeight = height(node.left);
  int rightHeight = height(node.right);
  if (Math.abs(leftHeight - rightHeight) > 1) return false;
  return isBalanced(node.left) && isBalanced(node.right);
}

✓ After

int checkHeight(Node node) {
  if (node == null) return 0;
  int leftHeight = checkHeight(node.left);
  if (leftHeight == -1) return -1;
  int rightHeight = checkHeight(node.right);
  if (rightHeight == -1) return -1;
  if (Math.abs(leftHeight - rightHeight) > 1) return -1;
  return Math.max(leftHeight, rightHeight) + 1;
}

boolean isBalanced(Node root) {
  return checkHeight(root) != -1;
}

What It Enables

This lets you quickly and reliably know if a tree is balanced, which is key for efficient searching and data handling.

Real Life Example

When building a phone contact list app, checking if the contact tree is balanced helps keep searches fast, so you find contacts quickly without delays.

Key Takeaways

Manual height checks are slow and error-prone.

Using a single pass with early stopping improves speed and accuracy.

Balanced trees keep data operations efficient and fast.

Practice

1. What does it mean for a binary tree to be balanced?

easy

A. The height difference between left and right subtrees of every node is at most 1

B. All nodes have two children

C. The tree has the same number of nodes on left and right

D. The tree is a complete binary tree

Solution

1. Step 1: Understand balance condition

   A balanced binary tree means the height difference between left and right subtrees of every node is at most 1.

2. Step 2: Compare other options

   Options A, B, and C describe different tree properties but not the balance condition.

3. Final Answer:

   The height difference between left and right subtrees of every node is at most 1 -> Option A

4. Quick Check:

   Balance means height difference ≤ 1 [OK]

Hint: Balance means height difference ≤ 1 at every node [OK]

Common Mistakes:

• Confusing balanced with complete tree
• Thinking balance means equal number of nodes
• Assuming all nodes must have two children

2. Which Java method signature correctly defines a function to check if a binary tree is balanced?

easy

A. boolean isBalanced(TreeNode root) void

B. public boolean isBalanced(TreeNode root)

C. public void isBalanced(TreeNode root) returns boolean

D. boolean isBalanced(TreeNode root) public

Solution

1. Step 1: Check Java method syntax

   Correct Java method signature includes access modifier, return type, method name, and parameters: public boolean isBalanced(TreeNode root)

2. Step 2: Identify incorrect syntax

   Options A, C, and D have invalid order or keywords not used in Java method declarations.

3. Final Answer:

   public boolean isBalanced(TreeNode root) -> Option B

4. Quick Check:

   Java method syntax: access returnType name(params) [OK]

Hint: Java method: access modifier + return type + name + parameters [OK]

Common Mistakes:

• Mixing return type and void
• Wrong keyword order
• Missing access modifier

3. What will be the output of the following code snippet?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int x) { val = x; }
}

public 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 node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.left.left = new TreeNode(5);
    Solution sol = new Solution();
    System.out.println(sol.isBalanced(root));
  }
}

medium

A. false

B. true

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Calculate subtree heights

   Left subtree of root has height 3 (nodes 2 -> 4 -> 5), right subtree has height 1 (node 3). Difference is 2 > 1.

2. Step 2: Check balance condition

   Since height difference > 1 at root, isBalanced returns false.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Height difference > 1 means unbalanced = false [OK]

Hint: Check height difference at root first for quick balance check [OK]

Common Mistakes:

• Ignoring height difference > 1
• Assuming tree is balanced by default
• Confusing height with node count

4. Identify the bug in this code snippet that checks if a binary tree is balanced:

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 node) {
  if (node == null) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

medium

A. Incorrect height calculation formula

B. Missing base case for null root

C. Using || instead of && in recursive call

D. No return statement in height method

Solution

1. Step 1: Analyze recursive calls

   The code uses || (OR) to combine left and right subtree balance checks, which returns true if either subtree is balanced.

2. Step 2: Correct logic for balance

   Both left and right subtrees must be balanced, so && (AND) should be used instead of ||.

3. Final Answer:

   Using || instead of && in recursive call -> Option C

4. Quick Check:

   Balance requires both subtrees balanced: use && [OK]

Hint: Use && to ensure both subtrees are balanced [OK]

Common Mistakes:

• Using || instead of &&
• Forgetting base case
• Miscomputing height

5. Given a binary tree, how can you optimize the balance check to avoid repeated height calculations?

hard

A. Use a queue to traverse nodes level by level

B. Calculate height separately for left and right subtrees multiple times

C. Only check balance at the root node

D. Calculate height and balance in one recursive function returning a special value

Solution

1. Step 1: Identify inefficiency in naive approach

   Naive method calculates height repeatedly for subtrees, causing extra work.

2. Step 2: Use combined recursive function

   Return height if subtree is balanced, else return -1 to indicate imbalance, avoiding repeated height calls.

3. Final Answer:

   Calculate height and balance in one recursive function returning a special value -> Option D

4. Quick Check:

   Combine height and balance check to optimize [OK]

Hint: Return -1 on imbalance to stop early and save time [OK]

Common Mistakes:

• Recalculating height multiple times
• Using level order traversal which doesn't help balance check
• Checking balance only at root