Check if Binary Tree is Balanced in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

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

beginner

Why is checking the height difference important in a balanced binary tree?

Because a large height difference means one side is much deeper, causing inefficient operations like search or insert.

intermediate

What is the time complexity of a naive approach to check if a binary tree is balanced?

The naive approach has O(n²) time complexity because it calculates height for each node repeatedly.

intermediate

How can we optimize the check for a balanced binary tree?

By calculating height and balance status in the same recursion, returning -1 if unbalanced, achieving O(n) time complexity.

intermediate

What does a return value of -1 indicate in the optimized balanced tree check?

It indicates that the subtree is not balanced, so no need to check further.

What is the maximum allowed height difference between left and right subtrees for a balanced binary tree?

A 1

B 0

C 2

D No limit

A balanced binary tree allows a height difference of at most 1 between left and right subtrees.

Which approach is more efficient to check if a binary tree is balanced?

A Calculate height separately for each node

B Traverse only left subtree

C Calculate height and balance in one recursion

D Traverse only right subtree

Calculating height and balance in one recursion avoids repeated height calculations, making it efficient.

What does a height return value of -1 mean in the optimized check?

A Subtree is empty

B Subtree is not balanced

C Subtree is balanced

D Height is zero

Returning -1 signals that the subtree is not balanced.

What is the time complexity of the optimized balanced tree check?

A O(n²)

B O(n log n)

C O(log n)

D O(n)

The optimized approach visits each node once, so time complexity is O(n).

If a node's left subtree height is 3 and right subtree height is 5, is the tree balanced at that node?

A No

B Only if right subtree is balanced

C Only if left subtree is balanced

D Yes

Height difference is 2, which is more than 1, so the node is not balanced.

Explain how to check if a binary tree is balanced using a single recursive function.

Think about combining height calculation and balance check in one step.

Describe why the naive approach to check if a binary tree is balanced can be inefficient.

Consider how many times height is computed for each node.

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