Check if Binary Tree is Balanced in DSA C++

Mental Model

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

Analogy: Imagine a tree with branches on both sides; if one side is much longer than the other, the tree might lean or fall. A balanced tree is like a well-trimmed tree with branches evenly spread.

      1
     / \
    2   3
   / 
  4  

(Heights differ by 1 or less at every node)

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2, right child 3; 2 has left child 4

Goal: Check if the tree is balanced by verifying height differences at every node

Step 1: Check leaf node 4: left and right children are null, so height is 1

Node 4: height=1, balanced=true

Why: Leaves have height 1 and are balanced by definition

Step 2: Check node 2: left subtree height=1 (from node 4), right subtree is null (height 0)

Node 2: left height=1, right height=0, difference=1, balanced=true

Why: Height difference 1 is allowed, so node 2 is balanced

Step 3: Check node 3: no children, height=1, balanced=true

Node 3: height=1, balanced=true

Why: Leaf node is balanced

Step 4: Check root node 1: left height=2 (from node 2), right height=1 (from node 3), difference=1

Node 1: balanced=true

Why: Height difference at root is 1, so tree is balanced

Result:

1 (root) balanced=true
Final answer: Tree is balanced

Annotated Code

DSA C++

#include <iostream>
#include <algorithm>
using namespace std;

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

// Returns height if balanced, -1 if not balanced
int checkHeight(TreeNode* root) {
    if (!root) return 0; // empty subtree height 0

    int leftHeight = checkHeight(root->left); // check left subtree
    if (leftHeight == -1) return -1; // left subtree not balanced

    int rightHeight = checkHeight(root->right); // check right subtree
    if (rightHeight == -1) return -1; // right subtree not balanced

    if (abs(leftHeight - rightHeight) > 1) return -1; // current node not balanced

    return max(leftHeight, rightHeight) + 1; // height of current node
}

bool isBalanced(TreeNode* root) {
    return checkHeight(root) != -1;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);

    cout << (isBalanced(root) ? "Tree is balanced" : "Tree is not balanced") << endl;
    return 0;
}

int leftHeight = checkHeight(root->left); // check left subtree

recursively get height of left subtree

if (leftHeight == -1) return -1; // left subtree not balanced

stop early if left subtree is unbalanced

int rightHeight = checkHeight(root->right); // check right subtree

recursively get height of right subtree

if (rightHeight == -1) return -1; // right subtree not balanced

stop early if right subtree is unbalanced

if (abs(leftHeight - rightHeight) > 1) return -1; // current node not balanced

check height difference at current node

return max(leftHeight, rightHeight) + 1; // height of current node

return height if balanced

Output

Tree is balanced

Complexity Analysis

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

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

vs Alternative: Naive approach recomputes heights repeatedly causing O(n^2) time; this method computes height and balance in one pass for O(n) time

Edge Cases

Empty tree

Returns balanced because empty tree has height 0 and no imbalance

DSA C++

if (!root) return 0; // empty subtree height 0

Single node tree

Returns balanced because single node has no children and height difference 0

DSA C++

if (!root) return 0; // empty subtree height 0

Unbalanced tree with large height difference

Returns not balanced (-1) as soon as difference > 1 is found

DSA C++

if (abs(leftHeight - rightHeight) > 1) return -1; // current node not balanced

When to Use This Pattern

When a problem asks if a tree is balanced, use a bottom-up height check with early stopping to efficiently detect imbalance.

Common Mistakes

Mistake: Calculating height separately for left and right subtrees multiple times causing O(n^2) time
Fix: Combine height calculation and balance check in one recursive function with early return

Mistake: Not stopping recursion early when imbalance is found, wasting time
Fix: Return -1 immediately when imbalance detected to stop further checks

Summary

Checks if a binary tree is balanced by verifying height differences at every node.

Use when you need to confirm tree balance efficiently in one traversal.

The key is to return height or -1 for imbalance in one recursive pass with early stopping.

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