Check if Binary Tree is Balanced in DSA Java

Mental Model

A balanced binary tree means no part is too tall compared to its sibling parts. We check if every node's left and right sides differ in height by at most one.

Analogy: Imagine a tree with branches on both sides. If one side is much taller than the other, the tree might fall. We want to make sure both sides grow evenly, like a well-trimmed bush.

      1
     / \
    2   3
   /   / \
  4   5   6

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2, right child 3; 2 has left child 4; 3 has children 5 and 6

Goal: Determine if the tree is balanced by checking height differences at every node

Step 1: Check leaf node 4: height is 0, balanced

Node 4: height=0, balanced=true

Why: Leaf nodes have height 0 and are balanced by definition

Step 2: Check node 2: left height=0 (from 4), right height=-1 (no right child), difference=1, balanced

Node 2: height=1, balanced=true

Why: Height difference is 1 which is allowed

Step 3: Check leaf nodes 5 and 6: heights=0, balanced=true

Node 5: height=0, balanced=true
Node 6: height=0, balanced=true

Why: Leaves are balanced

Step 4: Check node 3: left height=0 (5), right height=0 (6), difference=0, balanced

Node 3: height=1, balanced=true

Why: Equal heights means balanced

Step 5: Check root node 1: left height=1 (2), right height=1 (3), difference=0, balanced

Node 1: height=2, balanced=true

Why: Root is balanced because both sides have equal height

Result:

1 -> balanced=true
Final answer: The tree is balanced

Annotated Code

DSA Java

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

public class BalancedBinaryTree {
    static class Result {
        boolean balanced;
        int height;
        Result(boolean balanced, int height) {
            this.balanced = balanced;
            this.height = height;
        }
    }

    public static boolean isBalanced(TreeNode root) {
        return checkBalance(root).balanced;
    }

    private static Result checkBalance(TreeNode node) {
        if (node == null) {
            return new Result(true, -1); // empty tree height -1
        }

        Result left = checkBalance(node.left); // check left subtree
        if (!left.balanced) return new Result(false, 0); // left subtree not balanced

        Result right = checkBalance(node.right); // check right subtree
        if (!right.balanced) return new Result(false, 0); // right subtree not balanced

        boolean balanced = Math.abs(left.height - right.height) <= 1; // height difference check
        int height = Math.max(left.height, right.height) + 1; // current node height

        return new Result(balanced, height);
    }

    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.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);

        System.out.println(isBalanced(root));
    }
}

if (node == null) { return new Result(true, -1); }

Base case: empty subtree is balanced with height -1

Result left = checkBalance(node.left);

Recursively check left subtree balance and height

if (!left.balanced) return new Result(false, 0);

If left subtree is unbalanced, stop and return false

Result right = checkBalance(node.right);

Recursively check right subtree balance and height

if (!right.balanced) return new Result(false, 0);

If right subtree is unbalanced, stop and return false

boolean balanced = Math.abs(left.height - right.height) <= 1;

Check height difference between left and right subtrees

int height = Math.max(left.height, right.height) + 1;

Calculate current node height based on children

return new Result(balanced, height);

Return balance status and height for current node

Output

true

Complexity Analysis

Time: O(n) because we visit each node once to check balance and height

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach checks height separately for each node causing O(n^2) time; this method combines height and balance check in one pass for O(n)

Edge Cases

Empty tree (root is null)

Returns true since empty tree is balanced

DSA Java

if (node == null) { return new Result(true, -1); }

Single node tree

Returns true since single node is balanced

DSA Java

if (node == null) { return new Result(true, -1); }

Unbalanced tree with one side deeper by more than 1

Returns false when height difference > 1 detected

DSA Java

boolean balanced = Math.abs(left.height - right.height) <= 1;

When to Use This Pattern

When you need to check if a tree is balanced, use a bottom-up recursion that returns both height and balance status to avoid repeated height calculations.

Common Mistakes

Mistake: Calculating height separately for each node causing repeated work and O(n^2) time
Fix: Combine height and balance check in one recursive function returning both values

Mistake: Not checking balance of subtrees before comparing heights
Fix: Return immediately if left or right subtree is unbalanced to avoid unnecessary checks

Summary

Checks if a binary tree is balanced by ensuring height difference between left and right subtrees is at most one at every node.

Use when you want to verify tree balance efficiently without repeated height calculations.

The key insight is to return both height and balance status from each subtree in one recursion pass.

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