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 taller than the other, the tree is unbalanced and might fall. We check each branch to see if the tree stands evenly.

       1
      / \
     2   3
    /     \
   4       5

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 (which has left child 4), and right child 3 (which has right child 5)

Goal: Determine if the tree is balanced by checking height differences at each node

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

Node 4 height = 0

Why: Leaf nodes have height 0, base case for height calculation

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

Node 2 height = 1, balanced so far

Why: Height difference ≤ 1 means node 2 is balanced

Step 3: Check node 5: left and right children are null, height = 0

Node 5 height = 0

Why: Leaf node base case

Step 4: Check node 3: left height = -1 (null), right height = 0 (node 5), difference = 1

Node 3 height = 1, balanced so far

Why: Height difference ≤ 1 means node 3 is balanced

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

Node 1 height = 2, tree is balanced

Why: Height difference 0 means root is balanced, so whole tree is balanced

Result:

Tree is balanced

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <math.h> // Include math.h for abs function

// Define binary tree node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Helper function to check height and balance
int checkHeight(Node* root) {
    if (root == NULL) return -1; // base height for null

    int leftHeight = checkHeight(root->left); // height of left subtree
    if (leftHeight == -2) return -2; // left subtree not balanced

    int rightHeight = checkHeight(root->right); // height of right subtree
    if (rightHeight == -2) return -2; // right subtree not balanced

    if (abs(leftHeight - rightHeight) > 1) return -2; // current node unbalanced

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; // height of current node
}

// Main function to check if tree is balanced
int isBalanced(Node* root) {
    return checkHeight(root) != -2;
}

int main() {
    // Build tree from dry run example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->right = newNode(5);

    if (isBalanced(root)) {
        printf("Tree is balanced\n");
    } else {
        printf("Tree is not balanced\n");
    }

    return 0;
}

if (root == NULL) return -1; // base height for null

Return -1 height for empty subtree as base case

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

Recursively get left subtree height

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

Propagate unbalanced signal up if left subtree unbalanced

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

Recursively get right subtree height

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

Propagate unbalanced signal up if right subtree unbalanced

if (abs(leftHeight - rightHeight) > 1) return -2; // current node unbalanced

Check height difference; if too big, mark unbalanced

return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; // height of current node

Return height of current node as max child height plus one

return checkHeight(root) != -2;

Return true if tree balanced, false otherwise

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 checks balance at each node separately causing O(n^2) time; this method combines height and balance check in one pass for O(n)

Edge Cases

Empty tree (root is NULL)

Returns balanced because empty tree has no nodes to unbalance

DSA C

if (root == NULL) return -1; // base height for null

Single node tree

Returns balanced because single node has no children

DSA C

if (root == NULL) return -1; // base height for null

Unbalanced tree with one side deeper by more than 1

Returns not balanced when height difference > 1 detected

DSA C

if (abs(leftHeight - rightHeight) > 1) return -2; // current node unbalanced

When to Use This Pattern

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

Common Mistakes

Mistake: Calculating height and balance separately causing repeated work and O(n^2) time
Fix: Combine height calculation and balance check in one recursive function with early return on imbalance

Mistake: Returning 0 for null nodes instead of -1, causing off-by-one height errors
Fix: Return -1 for null nodes so leaf nodes have height 0 correctly

Summary

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

Use when you need to confirm a tree is balanced to ensure efficient operations like search or insert.

The key insight is to compute height and balance in one pass, returning a special value to signal imbalance early.

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

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

easy

A. bool isBalanced(struct Node root);

B. void isBalanced(struct Node root);

C. int isBalanced(Node root);

D. int isBalanced(struct Node* root);

Solution

1. Step 1: Check parameter type

   The function should take a pointer to the root node: struct Node* root.

2. Step 2: Check return type

   Return type int is common for boolean checks in C (0 or 1).

3. Final Answer:

   int isBalanced(struct Node* root); -> Option D

4. Quick Check:

   Pointer parameter and int return type [OK]

Hint: Use pointer to struct and int return for boolean in C [OK]

Common Mistakes:

• Passing struct by value instead of pointer
• Using void return type for boolean check
• Missing struct keyword in parameter

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

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

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

int isBalanced(struct Node* root) {
  if (!root) return 1;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  if (abs(leftHeight - rightHeight) > 1) return 0;
  return isBalanced(root->left) && isBalanced(root->right);
}

// Tree:
//     1
//    / \
//   2   3
//  /
// 4

int main() {
  struct Node n4 = {4, NULL, NULL};
  struct Node n2 = {2, &n4, NULL};
  struct Node n3 = {3, NULL, NULL};
  struct Node n1 = {1, &n2, &n3};
  printf("%d", isBalanced(&n1));
  return 0;
}

medium

A. Undefined behavior

B. 0

C. 1

D. Compilation error

Solution

1. Step 1: Calculate heights of subtrees

   Node 2's left subtree height is 1 (node 4), right subtree is 0, difference 1 ≤ 1. Node 1's left subtree height is 2, right subtree height is 1, difference 1 ≤ 1.

2. Step 2: Check balance recursively

   All nodes satisfy balance condition, so isBalanced returns 1 (true).

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Height difference ≤ 1 at all nodes means balanced [OK]

Hint: Check height difference ≤ 1 at every node recursively [OK]

Common Mistakes:

• Ignoring recursive balance check on subtrees
• Miscomputing height values
• Assuming difference > 0 means unbalanced

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

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

int isBalanced(struct Node* root) {
  if (!root) return 1;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  if (abs(leftHeight - rightHeight) > 1) return 0;
  return isBalanced(root->left) && isBalanced(root->right);
}

medium

A. abs function is not included from math.h

B. height function incorrectly sums left and right heights

C. isBalanced does not check for NULL root

D. isBalanced returns int instead of bool

Solution

1. Step 1: Analyze height function logic

   The height function incorrectly returns leftHeight + rightHeight + 1 instead of max(leftHeight, rightHeight) + 1.

2. Step 2: Understand impact on balance check

   Incorrect height causes wrong height difference, leading to wrong balance result.

3. Final Answer:

   height function incorrectly sums left and right heights -> Option B

4. Quick Check:

   Height = max(left, right) + 1, not sum [OK]

Hint: Height = max(left, right) + 1, not sum [OK]

Common Mistakes:

• Summing heights instead of taking max
• Ignoring NULL checks (though present here)
• Confusing return types for boolean

5. Given a binary tree where some nodes have only one child, which approach correctly checks if it is balanced? Choose the best method to implement isBalanced efficiently.

hard

A. Use a helper function that returns height and balance status simultaneously in one traversal

B. Calculate height for each node repeatedly in isBalanced causing O(n²) time

C. Check balance only at root node ignoring subtrees

D. Count total nodes and compare left and right subtree counts

Solution

1. Step 1: Understand naive approach

   Calculating height separately for each node causes repeated work and O(n²) time complexity.

2. Step 2: Efficient approach

   Using a helper function that returns both height and balance status in one traversal reduces time to O(n).

3. Final Answer:

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

4. Quick Check:

   Single traversal with combined info is efficient [OK]

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

Common Mistakes:

• Recomputing heights multiple times
• Ignoring subtree balance checks
• Using node counts instead of heights