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

Concept Flow - Check if Binary Tree is Balanced

Start at root

↓

Check left subtree height

↓

Check right subtree height

↓

Compare heights difference <= 1?

Yes | No↓

Check left balanced?

↓

Check right balanced?

Yes | No↓

Return true

Start from root, recursively check left and right subtree heights and balance, return false if difference > 1 or any subtree unbalanced.

Execution Sample

DSA C#

bool IsBalanced(TreeNode root) {
  if (root == null) return true;
  int leftHeight = Height(root.left);
  int rightHeight = Height(root.right);
  if (Math.Abs(leftHeight - rightHeight) > 1) return false;
  return IsBalanced(root.left) && IsBalanced(root.right);
}

int Height(TreeNode node) {
  if (node == null) return 0;
  return 1 + Math.Max(Height(node.left), Height(node.right));
}

Checks if binary tree is balanced by comparing heights of left and right subtrees recursively.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Difference	Balanced?	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 height at 5	5	1	1	0	true	5 / \ 3 7
6	Check right subtree height	15	-	-	-	-	15 \ 20
7	Check left subtree height	null	0	0	0	true	null
8	Check right subtree height	20	0	0	0	true	20 (leaf)
9	Calculate height at 15	15	0	1	1	true	15 \ 20
10	Calculate height at root 10	10	2	2	0	true	10 / \ 5 15 / \ \ 3 7 20
11	Check left balanced subtree	5	-	-	-	true	5 / \ 3 7
12	Check right balanced subtree	15	-	-	-	true	15 \ 20
13	Return final result	10	-	-	-	true	Tree is balanced
14	Exit	-	-	-	-	-	Balanced check complete

💡 All nodes checked, height differences <= 1, tree is balanced

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 9	After Step 10	Final
root	10	10	10	10	10	10
leftHeight (at 10)	-	-	2	-	2	2
rightHeight (at 10)	-	-	-	2	2	2
balanced (at 5)	-	-	true	-	-	true
balanced (at 15)	-	-	-	true	-	true
final balanced	-	-	-	-	-	true

Key Moments - 3 Insights

Why do we calculate height of left and right subtrees before checking balance?

Because balance depends on height difference. Execution table rows 2-10 show height calculation before balance check at each node.

What happens if height difference is more than 1 at any node?

The function returns false immediately, stopping further checks. See step 13 where all differences are <=1, so true is returned.

Why do we check balance recursively on left and right subtrees after height check?

Because even if height difference is okay at current node, subtrees might be unbalanced. Steps 11 and 12 show recursive balance checks.

Visual Quiz - 3 Questions

Look at the execution table, what is the height difference at root node (step 10)?

A 2

B 1

C 0

D Undefined

💡 Hint

Check 'Height Difference' column at step 10 in execution_table

At which step does the algorithm confirm the left subtree of root is balanced?

A Step 5

B Step 11

C Step 13

D Step 3

💡 Hint

Look for 'Balanced?' column and 'Check left balanced subtree' operation in execution_table

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

A Height difference would be 3 and balanced would be false

B Height difference would be 2 and balanced false

C Height difference would be 1 and balanced true

D No change in height difference or balance

💡 Hint

Height difference is absolute difference of left and right heights; check step 9 logic

Concept Snapshot

Check if Binary Tree is Balanced:
- Recursively find height of left and right subtrees
- If height difference > 1, tree is unbalanced
- Check balance recursively for left and right subtrees
- Return true only if all nodes satisfy balance condition
- Height of null node is 0
- Use post-order traversal for height and balance check

Full Transcript

This visualization shows how to check if a binary tree is balanced. Starting at the root node, we calculate the height of the left and right subtrees. The height is the number of edges on the longest path from the node down to a leaf. We then check if the absolute difference between these heights is more than 1. If yes, the tree is not balanced and we return false. If not, we recursively check if the left and right subtrees are balanced. This process continues until all nodes are checked. The execution table tracks each step, node visited, heights calculated, and balance status. The variable tracker shows how heights and balance flags change during execution. Key moments clarify why height is calculated first, what happens if difference is too big, and why recursive checks are needed. The quiz tests understanding of height difference, balance confirmation steps, and impact of subtree height changes. The snapshot summarizes the approach and key rules for balance checking in binary 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 sorted in ascending order

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 different properties not related to balance.

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 subtree heights differ by no more than 1 [OK]

Common Mistakes:

• Confusing balanced with complete or full tree
• Thinking balance means equal number of nodes
• Assuming sorted order means balanced

2. Which C# method signature correctly represents a function that checks if a binary tree is balanced?

easy

A. public bool IsBalanced(TreeNode root)

B. bool CheckBalance(int root)

C. public int IsBalanced(TreeNode root)

D. void IsBalanced(TreeNode root)

Solution

1. Step 1: Identify correct return type and parameters

   The function should return a boolean indicating if the tree is balanced and take the root node as input.

2. Step 2: Check method signature correctness

   public bool IsBalanced(TreeNode root) matches this: public bool IsBalanced(TreeNode root). Others have wrong return types or parameter types.

3. Final Answer:

   public bool IsBalanced(TreeNode root) -> Option A

4. Quick Check:

   Return bool, input TreeNode root [OK]

Hint: Check method returns bool and takes TreeNode root [OK]

Common Mistakes:

• Using int return type instead of bool
• Passing wrong parameter type like int
• Using void return type for a check function

3. Given the following tree structure and code, what will be the output?

class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int v) { val = v; }
}

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

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);

bool result = IsBalanced(root);
Console.WriteLine(result);

bool IsBalanced(TreeNode node) {
  if (node == null) return true;
  int leftHeight = Height(node.left);
  int rightHeight = Height(node.right);
  if (Math.Abs(leftHeight - rightHeight) > 1) return false;
  return IsBalanced(node.left) && IsBalanced(node.right);
}

int Height(TreeNode node) {
  if (node == null) return 0;
  return 1 + Math.Max(Height(node.left), Height(node.right));
}

medium

A. Runtime exception

B. false

C. Compilation error

D. true

Solution

1. Step 1: Calculate heights of subtrees

   Node 2 has left subtree height 1 (node 4) and right subtree height 0, difference is 1 (allowed). Node 1 has left height 2 and right height 1, difference is 1 (allowed).

2. Step 2: Check balance recursively

   Node 4 and 3 are leaves (balanced). However, node 2's left subtree is height 1 and right is 0, difference 1 (balanced). So all nodes satisfy balance condition.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Height difference ≤ 1 at all nodes = true [OK]

Hint: Check height difference at each node recursively [OK]

Common Mistakes:

• Miscounting subtree heights
• Not checking all nodes recursively
• Assuming difference > 0 means unbalanced

4. The following code is intended to check if a binary tree is balanced. What is the bug?

bool IsBalanced(TreeNode node) {
  if (node == null) return true;
  int leftHeight = Height(node.left);
  int rightHeight = Height(node.right);
  if (Math.Abs(leftHeight - rightHeight) > 1) return false;
  return IsBalanced(node.left) || IsBalanced(node.right);
}

int Height(TreeNode node) {
  if (node == null) return 0;
  return 1 + Math.Max(Height(node.left), Height(node.right));
}

medium

A. Missing null check for node

B. Using || instead of && in recursive calls

C. Height function returns wrong value

D. Incorrect base case in IsBalanced

Solution

1. Step 1: Analyze recursive condition

   The code uses || (OR) to combine left and right subtree balance checks, which returns true if either subtree is balanced.

2. Step 2: Correct logic for balance check

   Both left and right subtrees must be balanced, so && (AND) should be used instead of ||.

3. Final Answer:

   Using || instead of && in recursive calls -> Option B

4. Quick Check:

   Balance requires both subtrees balanced, use && [OK]

Hint: Use && to combine subtree balance checks [OK]

Common Mistakes:

• Using || instead of && in recursive checks
• Ignoring base case for null nodes
• Incorrect height calculation

5. You want to optimize the check for a balanced binary tree to avoid repeated height calculations. Which approach is best?

hard

A. Calculate height first, then check balance separately

B. Use BFS to check balance level by level

C. Calculate height and balance in one recursive function returning a tuple

D. Store heights in a global dictionary and update after each insertion

Solution

1. Step 1: Understand repeated height calculation problem

   Calculating height separately for each node causes repeated work, increasing time complexity.

2. Step 2: Use combined recursive approach

   Returning both height and balance status in one recursive call avoids repeated height calculations and improves efficiency.

3. Final Answer:

   Calculate height and balance in one recursive function returning a tuple -> Option C

4. Quick Check:

   Combine height and balance in one recursion for efficiency [OK]

Hint: Return height and balance together in one recursion [OK]

Common Mistakes:

• Separating height and balance checks causing repeated work
• Using BFS which doesn't directly check balance
• Using global dictionary unnecessarily complicates code