Check if Binary Tree is Balanced in DSA C - Deep Dive

Overview - Check if Binary Tree is Balanced

What is it?

A binary tree is balanced if for every node, the height difference between its left and right subtrees is at most one. Checking if a binary tree is balanced means verifying this condition for all nodes. This helps ensure the tree is well-structured for efficient operations like searching and inserting. Balanced trees avoid becoming too tall and skinny, which slows down these operations.

Why it matters

Without checking balance, a binary tree can become very uneven, like a long chain, making operations slow and inefficient. Balanced trees keep operations fast, which is crucial for programs that handle large amounts of data quickly. This check helps maintain performance and prevents worst-case slowdowns in real applications like databases or file systems.

Where it fits

Before this, you should understand what a binary tree is and how to find the height of a tree. After this, you can learn about self-balancing trees like AVL or Red-Black trees that automatically keep balance during insertions and deletions.

Mental Model

Core Idea

A binary tree is balanced if no node's left and right subtrees differ in height by more than one.

Think of it like...

Imagine a perfectly balanced seesaw where both sides are almost equal in weight; if one side is much heavier, the seesaw tips. Similarly, a balanced tree keeps its left and right sides nearly equal in height.

        Root
       /    \
   Left     Right
   Subtree  Subtree
    (h1)      (h2)

Balanced if |h1 - h2| ≤ 1 for every node

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Height

Concept: Learn how to find the height of a binary tree, which is the longest path from a node to a leaf.

The height of a node is 1 plus the maximum height of its left and right children. If a node is null, its height is 0. Example code in C: int height(struct Node* node) { if (node == NULL) return 0; int leftHeight = height(node->left); int rightHeight = height(node->right); return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); }

Result

Calling height on the root returns the total height of the tree.

Understanding height is essential because balance depends on comparing subtree heights at every node.

2

Foundation

Defining Balanced Binary Tree Condition

Concept: Introduce the balance condition: the height difference between left and right subtrees must be at most one for every node.

For each node, calculate the height of left and right subtrees. If the absolute difference is more than 1, the tree is not balanced. This condition must hold true for all nodes in the tree.

Result

You can now check if a single node is balanced by comparing subtree heights.

Knowing the exact balance condition helps us create a clear rule to check the entire tree.

3

Intermediate

Naive Balance Check Using Height

🤔Before reading on: do you think checking balance by computing height separately for each node is efficient or inefficient? Commit to your answer.

Concept: Check balance by computing height for each node's subtrees separately, then verify the balance condition recursively.

This method checks if left and right subtrees are balanced and then compares their heights. Example code snippet: int isBalanced(struct Node* root) { if (root == NULL) 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); }

Result

Returns 1 if balanced, 0 if not, but runs slowly for large trees.

This approach is simple but inefficient because it recalculates heights many times, leading to repeated work.

4

Intermediate

Optimized Single-Pass Balance Check

🤔Before reading on: do you think it's possible to check balance and height in one tree traversal? Commit to your answer.

Concept: Combine height calculation and balance check in one recursive function to avoid repeated height computations.

Create a helper function that returns the height if subtree is balanced, or -1 if not. Example code snippet: int checkHeight(struct Node* node) { if (node == NULL) return 0; int leftHeight = checkHeight(node->left); if (leftHeight == -1) return -1; int rightHeight = checkHeight(node->right); if (rightHeight == -1) return -1; if (abs(leftHeight - rightHeight) > 1) return -1; return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); } int isBalanced(struct Node* root) { return checkHeight(root) != -1; }

Result

Returns 1 if balanced, 0 if not, with much better performance.

Combining checks reduces time complexity from O(n²) to O(n), making it practical for large trees.

5

Advanced

Handling Edge Cases and Large Trees

🤔Before reading on: do you think very deep trees can cause problems with recursion? Commit to your answer.

Concept: Understand recursion limits and how very deep trees might cause stack overflow; consider iterative or tail-recursive approaches.

Deep trees can cause stack overflow in recursive functions. To handle this, iterative methods or tail recursion optimizations can be used. However, in C, tail call optimization is not guaranteed, so iterative traversal with explicit stack may be safer for very deep trees.

Result

Recognizing recursion limits helps avoid crashes in real applications.

Knowing recursion depth limits prevents runtime errors and guides safer implementation choices.

6

Expert

Integrating Balance Check in Self-Balancing Trees

🤔Before reading on: do you think balance checking is done separately or integrated in self-balancing trees? Commit to your answer.

Concept: In self-balancing trees like AVL, balance is checked and maintained during insertions and deletions, not by separate traversal.

AVL trees store height or balance factor at each node and update it during insert/delete operations. Balance checks trigger rotations to keep the tree balanced automatically. This avoids full tree traversal for balance checking after every change.

Result

Balance is maintained efficiently in real-time, ensuring optimal tree shape.

Understanding this integration explains why separate balance checks are rare in production and how AVL trees optimize performance.

Under the Hood

The balance check works by recursively calculating subtree heights and comparing them. The optimized method returns -1 immediately when imbalance is detected, stopping further checks. This short-circuiting saves time. Internally, the recursion stack holds nodes being processed, and height values propagate up the call stack. The absolute height difference condition ensures the tree remains shallow enough for efficient operations.

Why designed this way?

Originally, balance checks were separate and inefficient. The optimized approach was designed to reduce repeated height calculations, improving from O(n²) to O(n) time. This design balances simplicity and performance. Alternatives like storing heights at nodes require extra memory and updates, which AVL trees implement but simple checks do not.

checkHeight(node)
  ├─ if node is NULL: return 0
  ├─ leftHeight = checkHeight(node->left)
  │    └─ if leftHeight == -1: return -1 (unbalanced)
  ├─ rightHeight = checkHeight(node->right)
  │    └─ if rightHeight == -1: return -1 (unbalanced)
  ├─ if |leftHeight - rightHeight| > 1: return -1 (unbalanced)
  └─ return 1 + max(leftHeight, rightHeight)

isBalanced(root) = (checkHeight(root) != -1)

Myth Busters - 4 Common Misconceptions

Quick: Does a balanced tree always have the same number of nodes on left and right? Commit yes or no.

Common Belief: Many think a balanced tree means equal number of nodes on left and right subtrees.

Reality: Balance depends on height difference, not node count. Subtrees can have different numbers of nodes but still be balanced if heights differ by at most one.

Why it matters: Confusing node count with height can lead to wrong balance checks and inefficient tree designs.

Quick: Is it okay to check balance by only looking at the root node? Commit yes or no.

Common Belief: Some believe checking the root's subtree heights is enough to decide if the whole tree is balanced.

Reality: Balance must be checked at every node, not just the root. A subtree deep inside can be unbalanced even if the root looks balanced.

Why it matters: Ignoring internal nodes can cause missed imbalances, leading to poor performance.

Quick: Does the naive height-based balance check run in linear time? Commit yes or no.

Common Belief: People often think the simple recursive height check is efficient enough for all trees.

Reality: Naive approach runs in O(n²) time because it recalculates heights repeatedly, which is slow for large trees.

Why it matters: Using naive checks in large systems causes slowdowns and wasted resources.

Quick: Can balance checking alone fix an unbalanced tree? Commit yes or no.

Common Belief: Some think that just checking balance will automatically fix the tree.

Reality: Balance checking only detects imbalance; fixing requires rotations or restructuring, as done in AVL or Red-Black trees.

Why it matters: Relying on checking alone without fixing leads to persistent inefficiencies.

Expert Zone

1

Balance checking can be combined with other tree operations to avoid extra traversals, improving performance in complex algorithms.

2

In some applications, a relaxed balance condition (allowing height difference up to 2) is acceptable to reduce rotations and improve insertion speed.

3

Memory overhead of storing height or balance factor at each node is a tradeoff between faster balance checks and increased space usage.

When NOT to use

Separate balance checking is not suitable for real-time systems requiring fast insertions/deletions; use self-balancing trees like AVL or Red-Black trees instead. For very large or deep trees, iterative or non-recursive methods are preferred to avoid stack overflow.

Production Patterns

In production, balance checks are integrated into insertion and deletion operations in AVL trees. Systems like databases use balanced trees to maintain quick search times. Balance checking is often combined with caching subtree heights or balance factors to optimize performance.

Connections

AVL Trees

Builds-on

Understanding balance checking is foundational to grasping how AVL trees maintain balance automatically during updates.

Divide and Conquer Algorithms

Same pattern

Balance checking uses divide and conquer by breaking the problem into checking left and right subtrees, then combining results.

Structural Engineering

Analogous principle

Just like balanced trees ensure stability in data, structural engineers ensure buildings are balanced to prevent collapse, showing how balance is a universal concept in stability.

Common Pitfalls

#1 Recomputing height for every node separately causes slow performance.

Wrong approach:

int isBalanced(struct Node* root) {
if (root == NULL) 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);
}

Correct approach:

int checkHeight(struct Node* node) {
if (node == NULL) return 0;
int leftHeight = checkHeight(node->left);
if (leftHeight == -1) return -1;
int rightHeight = checkHeight(node->right);
if (rightHeight == -1) return -1;
if (abs(leftHeight - rightHeight) > 1) return -1;
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int isBalanced(struct Node* root) {
return checkHeight(root) != -1;
}

Root cause:

Not combining height calculation and balance check leads to repeated work and inefficiency.

#2 Checking balance only at the root node and ignoring subtrees.

Wrong approach:

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

Correct approach:

int isBalanced(struct Node* root) {
if (root == NULL) 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);
}

Root cause:

Balance must be checked at every node, not just the root.

#3 Assuming balanced means equal number of nodes on both sides.

Wrong approach:

if (countNodes(root->left) == countNodes(root->right)) {
// assume balanced
}

Correct approach:

Check height difference instead of node count:
if (abs(height(root->left) - height(root->right)) <= 1) {
// balanced
}

Root cause:

Confusing node count with height leads to incorrect balance checks.

Key Takeaways

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

Naive balance checks that compute height repeatedly are inefficient; combining height and balance checks in one traversal is optimal.

Balance must be checked at every node, not just the root, to ensure the entire tree is balanced.

In real systems, balance checking is integrated with tree updates to maintain performance automatically.

Understanding balance checking is essential before learning self-balancing trees like AVL or Red-Black trees.

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