Check if Binary Tree is Balanced in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced Check on Simple Tree

What is the output of the following C# code that checks if a binary tree is balanced?

DSA C#

using System;

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

class Program {
    static int CheckHeight(Node root) {
        if (root == null) return 0;
        int leftHeight = CheckHeight(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = CheckHeight(root.right);
        if (rightHeight == -1) return -1;
        if (Math.Abs(leftHeight - rightHeight) > 1) return -1;
        return Math.Max(leftHeight, rightHeight) + 1;
    }

    static bool IsBalanced(Node root) {
        return CheckHeight(root) != -1;
    }

    static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        Console.WriteLine(IsBalanced(root));
    }
}

A False

B Compile-time error

C True

D Runtime exception

💡 Hint

Think about the height difference between left and right subtrees at each node.

The tree is balanced because for every node, the height difference between left and right subtrees is at most 1.

❓ Predict Output

intermediate

Output for Unbalanced Tree Check

What is the output of this C# code that checks if a binary tree is balanced?

DSA C#

using System;

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

class Program {
    static int CheckHeight(Node root) {
        if (root == null) return 0;
        int leftHeight = CheckHeight(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = CheckHeight(root.right);
        if (rightHeight == -1) return -1;
        if (Math.Abs(leftHeight - rightHeight) > 1) return -1;
        return Math.Max(leftHeight, rightHeight) + 1;
    }

    static bool IsBalanced(Node root) {
        return CheckHeight(root) != -1;
    }

    static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(3);
        root.left.left.left = new Node(4);
        Console.WriteLine(IsBalanced(root));
    }
}

A True

B False

C Compile-time error

D Runtime exception

💡 Hint

Check the height difference at the root node.

The tree is unbalanced because the left subtree is much deeper than the right subtree (which is null).

🧠 Conceptual

advanced

Understanding the Balance Check Algorithm

Which statement best describes why the CheckHeight function returns -1?

A It indicates the subtree is unbalanced.

B It indicates the subtree is balanced.

C It indicates the subtree is empty.

D It indicates the subtree has equal left and right heights.

💡 Hint

Think about what the special value -1 signals in the recursion.

Returning -1 signals that the subtree is unbalanced, so the algorithm can stop checking further.

🔧 Debug

advanced

Identify the Bug in Balance Check Code

What error will this code produce when checking if a binary tree is balanced?

DSA C#

using System;

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

class Program {
    static int CheckHeight(Node root) {
        if (root == null) return 0;
        int leftHeight = CheckHeight(root.left);
        int rightHeight = CheckHeight(root.right);
        if (Math.Abs(leftHeight - rightHeight) > 1) return -1;
        return Math.Max(leftHeight, rightHeight) + 1;
    }

    static bool IsBalanced(Node root) {
        return CheckHeight(root) != -1;
    }

    static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(3);
        root.left.left.left = new Node(4);
        Console.WriteLine(IsBalanced(root));
    }
}

A No error, outputs True

B No error, outputs False

C StackOverflowException due to infinite recursion

D Incorrect result because unbalanced subtree not detected

💡 Hint

Check if the function stops checking after detecting unbalance.

The code does not check if leftHeight or rightHeight is -1 before continuing, so it misses unbalanced subtrees.

🚀 Application

expert

Count Balanced Subtrees in a Binary Tree

Given a binary tree, which code snippet correctly counts how many subtrees are balanced?

DSA C#

using System;

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

class Program {
    static int balancedCount = 0;

    static int CheckHeightAndCount(Node root) {
        if (root == null) return 0;
        int leftHeight = CheckHeightAndCount(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = CheckHeightAndCount(root.right);
        if (rightHeight == -1) return -1;
        if (Math.Abs(leftHeight - rightHeight) > 1) return -1;
        balancedCount++;
        return Math.Max(leftHeight, rightHeight) + 1;
    }

    static int CountBalancedSubtrees(Node root) {
        balancedCount = 0;
        CheckHeightAndCount(root);
        return balancedCount;
    }

    static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.left.left.left = new Node(6);
        Console.WriteLine(CountBalancedSubtrees(root));
    }
}

A 5

B 6

C 4

D 3

💡 Hint

Count every subtree that is balanced including leaf nodes.

The code counts all balanced subtrees. The tree has 5 balanced subtrees including leaves and some internal nodes.

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