Check if Binary Tree is Balanced in DSA C - Build from Scratch

Check if Binary Tree is Balanced

📖 Scenario: You are working on a program that manages a binary tree data structure. A balanced binary tree is one where the difference in height between the left and right subtrees of every node is at most 1. This helps keep operations efficient.Your task is to write code that checks if a given binary tree is balanced.

🎯 Goal: Build a C program that creates a binary tree, sets up a helper function to check balance, implements the logic to check if the tree is balanced, and prints the result.

📋 What You'll Learn

Create a binary tree node structure with integer data and left/right pointers

Manually create a binary tree with the exact nodes and structure given

Write a helper function to calculate the height of a subtree

Write a function to check if the binary tree is balanced

Print 1 if the tree is balanced, 0 if not

💡 Why This Matters

🌍 Real World

Balanced binary trees are used in databases and file systems to keep data organized for fast searching and updating.

💼 Career

Understanding tree balance is important for software engineers working on performance-critical applications and data structure implementations.

1

Create the binary tree structure and nodes

Define a struct called Node with an int data and two pointers left and right. Then create nodes to form this exact tree:

1
/ \
2 3
/
4

Use malloc to allocate each node and assign the data values 1, 2, 3, and 4 accordingly. Connect the nodes to form the tree.

DSA C

#include 
#include 

// Define Node struct and create tree nodes
// Your code here

Hint

Start by defining the Node struct with data, left, and right. Then use malloc to create each node and assign the data values. Connect the nodes by setting the left and right pointers.

2

Add a helper function to calculate height

Write a function called height that takes a Node* called root and returns an int. It should return 0 if root is NULL. Otherwise, it should return 1 plus the maximum height of the left and right subtrees.

DSA C

#include 
#include 

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

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = (Node*)malloc(sizeof(Node));
    root->left->data = 2;
    root->right = (Node*)malloc(sizeof(Node));
    root->right->data = 3;
    root->left->left = (Node*)malloc(sizeof(Node));
    root->left->left->data = 4;
    root->left->right = NULL;
    root->right->left = NULL;
    root->right->right = NULL;
    root->left->left->left = NULL;
    root->left->left->right = NULL;

    return 0;
}

// Write the height function below
// Your code here

Hint

The height of a tree is 0 if the node is NULL. Otherwise, find the height of the left and right children recursively, then return the bigger one plus 1.

3

Write the function to check if the tree is balanced

Write a function called isBalanced that takes a Node* called root and returns an int. It should return 1 if the tree is balanced and 0 if not. Use the height function. The tree is balanced if the absolute difference between the heights of the left and right subtrees is at most 1, and both subtrees are balanced.

DSA C

#include 
#include 

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

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

// Write the isBalanced function below
// Your code here

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = (Node*)malloc(sizeof(Node));
    root->left->data = 2;
    root->right = (Node*)malloc(sizeof(Node));
    root->right->data = 3;
    root->left->left = (Node*)malloc(sizeof(Node));
    root->left->left->data = 4;
    root->left->right = NULL;
    root->right->left = NULL;
    root->right->right = NULL;
    root->left->left->left = NULL;
    root->left->left->right = NULL;

    return 0;
}

Hint

Check if the current node is NULL (balanced). Then get the heights of left and right subtrees. If their difference is more than 1, return 0. Also check recursively if left and right subtrees are balanced.

4

Print if the tree is balanced

Use printf to print the result of isBalanced(root). This will print 1 if the tree is balanced, or 0 if it is not.

DSA C

#include 
#include 
#include 

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

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

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

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = (Node*)malloc(sizeof(Node));
    root->left->data = 2;
    root->right = (Node*)malloc(sizeof(Node));
    root->right->data = 3;
    root->left->left = (Node*)malloc(sizeof(Node));
    root->left->left->data = 4;
    root->left->right = NULL;
    root->right->left = NULL;
    root->right->right = NULL;
    root->left->left->left = NULL;
    root->left->left->right = NULL;

    // Print if the tree is balanced
    // Your code here

    return 0;
}

Hint

Call isBalanced(root) inside printf to print the result. It will print 1 if balanced, 0 if not.

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