Check if Binary Tree is Balanced in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced Binary Tree Check

What is the output of the following Java code that checks if a binary tree is balanced?

DSA Java

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

public class Main {
    public static boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }

    private static int checkHeight(TreeNode 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;
    }

    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);
        System.out.println(isBalanced(root));
    }
}

A Compilation error

B true

C false

D Runtime exception

💡 Hint

Think about the height difference between left and right subtrees at each node.

The tree is unbalanced because the left subtree of the root has a height difference greater than 1 compared to the right subtree. The method returns false.

❓ Predict Output

intermediate

Output of Balanced Check on Perfect Binary Tree

What will be printed when running this code that checks if a perfect binary tree is balanced?

DSA Java

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

public class Main {
    public static boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }

    private static int checkHeight(TreeNode 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;
    }

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

A true

B false

C Compilation error

D Runtime exception

💡 Hint

A perfect binary tree is always balanced.

All leaf nodes are at the same level and the height difference between left and right subtrees of every node is 0 or 1, so the tree is balanced.

🔧 Debug

advanced

Identify the error in this balanced tree check code

What error will this Java code produce when checking if a binary tree is balanced?

DSA Java

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

public class Main {
    public static boolean isBalanced(TreeNode root) {
        return checkHeight(root) != 0;
    }

    private static int checkHeight(TreeNode 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;
    }
}

A Logical error: incorrect condition in isBalanced

B Always returns true

C Compilation error

D Always returns false

💡 Hint

Check the condition used to decide if the tree is balanced.

The isBalanced method incorrectly compares checkHeight(root) != 0 instead of != -1. This causes wrong results because 0 means empty tree (balanced), but the method expects -1 for unbalanced.

🧠 Conceptual

advanced

Understanding Balanced Binary Tree Definition

Which of the following best describes the condition for a binary tree to be balanced?

A The tree has the minimum possible height

B The difference between the heights of left and right subtrees of every node is at most 1

C All leaf nodes are at the same depth

D The difference between the number of nodes in left and right subtrees of every node is at most 1

💡 Hint

Balance depends on subtree heights, not node counts.

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

❓ Predict Output

expert

Output of Balanced Check on Large Unbalanced Tree

What is the output of this code that checks if a large unbalanced binary tree is balanced?

DSA Java

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

public class Main {
    public static boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }

    private static int checkHeight(TreeNode 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;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode current = root;
        for (int i = 2; i <= 10; i++) {
            current.left = new TreeNode(i);
            current = current.left;
        }
        System.out.println(isBalanced(root));
    }
}

A true

B StackOverflowError

C Compilation error

D false

💡 Hint

A long chain on one side makes the tree unbalanced.

The tree is a linked list going left only, so height difference at root is large, making it unbalanced.

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