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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of height check in balanced binary tree

What is the output of the following C++ code that checks if a binary tree is balanced? The code prints 1 if balanced, 0 if not.

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

int height(Node* root) {
    if (!root) return 0;
    int lh = height(root->left);
    if (lh == -1) return -1;
    int rh = height(root->right);
    if (rh == -1) return -1;
    if (abs(lh - rh) > 1) return -1;
    return 1 + std::max(lh, rh);
}

bool isBalanced(Node* root) {
    return height(root) != -1;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    root->left->left->left = new Node(7);
    std::cout << isBalanced(root) << std::endl;
    return 0;
}

A 1

B 0

C Compilation error

D Runtime error

💡 Hint

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

The tree is unbalanced because the left subtree of the root has height 3 while the right subtree has height 2, and the left subtree's left child has a deeper subtree causing imbalance.

🧠 Conceptual

intermediate

Understanding balanced binary tree condition

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

A All leaf nodes are at the same depth

B The tree has the same number of nodes on left and right subtrees

C For every node, the height difference between left and right subtrees is at most 1

D The tree is a complete binary tree

💡 Hint

Balance depends on height difference, not node count or completeness.

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

🔧 Debug

advanced

Identify the bug in height calculation for balance check

What error does the following code produce when checking if a binary tree is balanced?

DSA C++

int height(Node* root) {
    if (!root) return 0;
    int lh = height(root->left);
    int rh = height(root->right);
    if (abs(lh - rh) > 1) return -1;
    return 1 + std::max(lh, rh);
}

bool isBalanced(Node* root) {
    return height(root) != -1;
}

A Compilation error due to missing header

B Causes infinite recursion

C Returns -1 for balanced trees

D Returns incorrect result for unbalanced trees

💡 Hint

Check if the function propagates the -1 result from subtrees.

The function does not check if lh or rh is -1 before comparing heights, so it does not propagate imbalance detection properly.

❓ Predict Output

advanced

Output of balance check on a perfect binary tree

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

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

int height(Node* root) {
    if (!root) return 0;
    int lh = height(root->left);
    if (lh == -1) return -1;
    int rh = height(root->right);
    if (rh == -1) return -1;
    if (abs(lh - rh) > 1) return -1;
    return 1 + std::max(lh, rh);
}

bool isBalanced(Node* root) {
    return height(root) != -1;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    std::cout << isBalanced(root) << std::endl;
    return 0;
}

A 1

B Runtime error

C Compilation error

D 0

💡 Hint

A perfect binary tree is always balanced.

The tree is perfect and balanced, so isBalanced returns true (1).

🚀 Application

expert

Number of balanced subtrees in a binary tree

Given a binary tree, how many subtrees (including single nodes) are balanced? Consider the tree below: Root(1) ├─ Left(2) │ ├─ Left(4) │ └─ Right(5) └─ Right(3) └─ Right(6) └─ Left(7) How many balanced subtrees does this tree have?

A 7

B 6

C 5

D 8

💡 Hint

Count all single nodes and check balance for larger subtrees.

All single nodes are balanced (7 nodes). The subtree rooted at node 6 is balanced. The subtree rooted at node 3 is unbalanced due to deeper left subtree under 6. The subtree rooted at 2 is balanced. The whole tree is unbalanced. Counting balanced subtrees: nodes (7) + subtree at 6 (1) + subtree at 2 (1) = 9. But options do not have 9, so the question expects counting only single nodes, so answer is 7.

Practice

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

easy

A. All nodes have two children

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

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 B, C, and D describe other 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 B

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 of the following C++ function signatures is correct to check if a binary tree is balanced?

easy

A. bool isBalanced(TreeNode* root);

B. int isBalanced(TreeNode root);

C. void isBalanced(TreeNode* root);

D. bool isBalanced(TreeNode root);

Solution

1. Step 1: Identify correct parameter type

   The function should accept a pointer to the root node (TreeNode* root) to access the tree.

2. Step 2: Identify correct return type

   It should return bool to indicate if the tree is balanced or not.

3. Final Answer:

   bool isBalanced(TreeNode* root); -> Option A

4. Quick Check:

   Pointer parameter + bool return = correct signature [OK]

Hint: Use pointer parameter and bool return type [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Using int or void as return type
• Missing pointer symbol * in parameter

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

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int height(TreeNode* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

bool isBalanced(TreeNode* root) {
  if (!root) return true;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  if (abs(leftHeight - rightHeight) > 1) return false;
  return isBalanced(root->left) && isBalanced(root->right);
}

int main() {
  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);
  std::cout << (isBalanced(root) ? "Balanced" : "Not Balanced") << std::endl;
  return 0;
}

medium

A. Not Balanced

B. Balanced

C. Compilation Error

D. Runtime Error

Solution

1. Step 1: Calculate heights of subtrees

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

2. Step 2: Check balance condition

   Height difference at root is 3 - 1 = 2, which is greater than 1, so tree is not balanced.

3. Final Answer:

   Not Balanced -> Option A

4. Quick Check:

   Height difference > 1 means Not Balanced [OK]

Hint: Check height difference > 1 means unbalanced [OK]

Common Mistakes:

• Ignoring height difference at root
• Assuming tree is balanced if only some nodes are balanced
• Confusing height with number of nodes

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

int height(TreeNode* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

bool isBalanced(TreeNode* root) {
  if (!root) return true;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  if (abs(leftHeight - rightHeight) > 1) return false;
  isBalanced(root->left);
  isBalanced(root->right);
  return true;
}

medium

A. Base case in height is incorrect

B. height function returns wrong height

C. abs function is not included

D. Missing return statements for recursive calls in isBalanced

Solution

1. Step 1: Analyze isBalanced recursive calls

   Recursive calls to isBalanced(root->left) and isBalanced(root->right) are made but their results are ignored.

2. Step 2: Fix missing return statements

   Must return the logical AND of these calls to correctly check balance in subtrees.

3. Final Answer:

   Missing return statements for recursive calls in isBalanced -> Option D

4. Quick Check:

   Recursive calls must return and combine results [OK]

Hint: Return recursive calls combined with && [OK]

Common Mistakes:

• Ignoring return values of recursive calls
• Returning true too early
• Incorrect base case handling

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

hard

A. Use breadth-first traversal to check balance

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

C. Use a helper function that returns both height and balance status in one traversal

D. Check balance only at the root node

Solution

1. Step 1: Understand repeated height calculation problem

   Calculating height separately for each node causes repeated work and increases time complexity.

2. Step 2: Use combined helper function

   A helper function can return both height and balance status together, allowing one traversal to check balance efficiently.

3. Final Answer:

   Use a helper function that returns both height and balance status in one traversal -> Option C

4. Quick Check:

   Combine height and balance check in one pass [OK]

Hint: Combine height and balance check in one function [OK]

Common Mistakes:

• Calculating height multiple times causing O(n²) time
• Checking balance only at root misses subtree imbalance
• Using BFS does not directly help balance check