Check if Binary Tree is Balanced in DSA C - Execution Trace

Concept Flow - Check if Binary Tree is Balanced

Start at root node

↓

Check left subtree height

↓

Check right subtree height

↓

Compare heights difference <= 1?

Yes↓

Check if left subtree balanced

↓

Check if right subtree balanced

Yes↓

Return True (balanced)

No↓

Return False (not balanced)

The process checks the height of left and right subtrees at each node, compares their difference, and recursively verifies balance for subtrees.

Execution Sample

DSA C

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

int isBalanced(Node* root) {
  if (!root) return 1;
  int lh = height(root->left);
  int rh = height(root->right);
  if (abs(lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right))
    return 1;
  return 0;
}

This code checks if a binary tree is balanced by comparing subtree heights and recursively checking subtrees.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Difference	Balanced Check	Visual State
1	Start at root	10	-	-	-	-	10 / \ 5 15
2	Check left subtree height	5	-	-	-	-	5 / \ 3 7
3	Check left subtree height	3	0	0	0	True	3 (leaf)
4	Check right subtree height	7	0	0	0	True	7 (leaf)
5	Calculate left height of 5	5	1	1	0	True	5 subtree balanced
6	Check right subtree height	15	-	-	-	-	15 / \ 12 20
7	Check left subtree height	12	0	0	0	True	12 (leaf)
8	Check right subtree height	20	0	0	0	True	20 (leaf)
9	Calculate right height of 15	15	1	1	0	True	15 subtree balanced
10	Calculate root height difference	10	2	2	0	True	Whole tree balanced
11	Return result	10	-	-	-	True	Balanced tree confirmed

💡 All nodes checked, height differences <= 1, and all subtrees balanced, so tree is balanced.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 7	After Step 8	After Step 9	After Step 10	Final
root	Node 10	Node 10	Node 10	Node 10	Node 10	Node 10	Node 10	Node 10	Node 10
lh (left height)	-	1	1	1	1	1	1	2	2
rh (right height)	-	-	-	-	-	1	1	2	2
height difference	-	-	-	0	-	-	0	0	0
balanced	-	True	True	True	True	True	True	True	True

Key Moments - 3 Insights

Why do we check height difference at every node instead of just at the root?

Because balance must hold at every node, not just the root. The execution_table rows 5, 9, and 10 show height differences checked at each node to ensure full tree balance.

What happens if a subtree is NULL (empty)?

An empty subtree has height 0 and is considered balanced. This is shown in rows 3, 4, 7, and 8 where leaf nodes have left and right heights 0.

Why do we need to check both isBalanced(left) and isBalanced(right)?

Because even if height difference is small, subtrees themselves might be unbalanced. Rows 5 and 9 confirm both subtrees are balanced before confirming the node is balanced.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the height difference at node 5?

A 1

B 2

C 0

D Undefined

💡 Hint

Check the 'Height Difference' column in row for step 5.

At which step does the algorithm confirm the whole tree is balanced?

A Step 10

B Step 7

C Step 9

D Step 3

💡 Hint

Look at the 'Balanced Check' and 'Visual State' columns for the final confirmation.

If the left subtree of node 15 had height 3 instead of 1, what would happen at step 9?

A Height difference would be 0 and balanced check True

B Height difference would be 2 and balanced check would be False

C Algorithm would skip step 9

D Height difference would be 1 and balanced check True

💡 Hint

Compare height difference calculation in 'Height Difference' column at step 9.

Concept Snapshot

Check if Binary Tree is Balanced:
- For each node, find left and right subtree heights.
- If height difference > 1, tree is unbalanced.
- Recursively check left and right subtrees.
- Return True only if all nodes satisfy balance condition.
- Base case: empty subtree is balanced with height 0.

Full Transcript

This concept checks if a binary tree is balanced by measuring the height of left and right subtrees at every node. Starting from the root, it calculates subtree heights, compares their difference, and recursively verifies balance for each subtree. If any node has a height difference greater than 1, the tree is not balanced. Empty subtrees count as height 0 and are balanced. The process continues until all nodes are checked, returning True if balanced or False otherwise.

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