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.