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. This means the tree is not too lopsided or skewed on one side. Checking if a binary tree is balanced helps ensure operations like search, insert, and delete stay efficient. It is a common problem in tree data structures to maintain performance.

Why it matters

Without checking balance, a binary tree can become very uneven, like a tall skinny tree, which slows down operations to linear time instead of logarithmic. This can make programs slow and inefficient, especially with large data. Balanced trees keep data organized so computers can find and update information quickly, improving user experience and saving resources.

Where it fits

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

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 seesaw with two kids sitting on each side. If one side is much heavier or taller, the seesaw tips and is unbalanced. A balanced binary tree is like a seesaw that stays level because both sides are almost equal in weight.

       Node
      /    \
  Left     Right
  Subtree  Subtree
  (height h1) (height h2)

Balanced if |h1 - h2| <= 1

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 the root to a leaf.

The height of a node is 1 plus the maximum height of its left and right children. A leaf node has height 1. We use recursion to find height: if node is null, height is 0; else height = 1 + max(height(left), height(right)).

Result

You can calculate the height of any node or the whole tree.

Knowing how to measure height is essential because balance depends on comparing subtree heights.

2

Foundation

What Does Balanced Mean in Trees?

Concept: Define the balance condition: difference in heights of left and right subtrees is at most one for every node.

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

Result

You understand the exact rule that decides if a tree is balanced or not.

Balance is a local property checked at every node, not just the root.

3

Intermediate

Naive Balance Check Using Separate Height Calls

🤔Before reading on: do you think calling height separately for each node is efficient or slow? Commit to your answer.

Concept: Check balance by computing height for each node's subtrees separately, then check difference.

For each node, recursively get height of left and right subtrees, then check difference. Recursively check if left and right subtrees are balanced. This leads to repeated height calculations.

Result

Correctly identifies balanced or unbalanced trees but can be slow for large trees.

Understanding this naive approach shows why repeated work can cause inefficiency.

4

Intermediate

Optimized Single-Pass Balance Check

🤔Before reading on: can you think of a way to check balance and height in one go? Commit to your answer.

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

Write a function that returns height if subtree is balanced, else returns -1. For each node, get left and right heights. If either is -1 or difference > 1, return -1. Else return 1 + max(left, right). If final result is -1, tree is unbalanced.

Result

Efficiently checks balance in O(n) time by avoiding repeated height calls.

Knowing how to combine checks reduces time complexity from O(n^2) to O(n).

5

Advanced

Implementing Balance Check in C++

🤔Before reading on: predict the output of the code on a balanced and unbalanced tree example.

Concept: Write complete C++ code using the optimized approach to check if a binary tree is balanced.

```cpp #include #include #include using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; int checkHeight(TreeNode* root) { if (!root) return 0; int leftHeight = checkHeight(root->left); if (leftHeight == -1) return -1; int rightHeight = checkHeight(root->right); if (rightHeight == -1) return -1; if (abs(leftHeight - rightHeight) > 1) return -1; return 1 + max(leftHeight, rightHeight); } bool isBalanced(TreeNode* root) { return checkHeight(root) != -1; } int main() { TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); cout << (isBalanced(root) ? "Balanced" : "Not Balanced") << endl; root->left->left->left = new TreeNode(6); cout << (isBalanced(root) ? "Balanced" : "Not Balanced") << endl; return 0; } ```

Result

Balanced Not Balanced

Seeing the full code and output confirms how the optimized approach works in practice.

6

Expert

Why Balance Check is O(n) and Not More

🤔Before reading on: do you think the optimized balance check visits nodes multiple times or just once? Commit to your answer.

Concept: Analyze why the optimized method visits each node only once, making it efficient.

The function checkHeight visits each node once, computing height and balance status simultaneously. It returns early (-1) if imbalance is found, avoiding unnecessary checks. This single traversal ensures O(n) time complexity, where n is number of nodes.

Result

Understanding the time complexity and early stopping behavior.

Knowing this prevents inefficient implementations and helps optimize tree algorithms.

Under the Hood

The balance check uses recursion to traverse the tree from bottom to top. At each node, it calculates the height of left and right subtrees. If any subtree is unbalanced (returns -1), it propagates this signal up immediately. Otherwise, it returns the height plus one. This mechanism ensures each node is processed once, and imbalance detection short-circuits further checks.

Why designed this way?

Originally, balance checks were done by separate height calls causing repeated work and O(n^2) time. The optimized design merges height and balance checks to improve efficiency. Early stopping on imbalance saves time in large trees. This design balances clarity and performance.

  ┌───────────────┐
  │   checkHeight │
  └──────┬────────┘
         │
   ┌─────▼─────┐
   │  Node N   │
   └─────┬─────┘
         │
 ┌───────▼───────┐       ┌───────────────┐
 │checkHeight(L) │       │checkHeight(R) │
 └───────┬───────┘       └───────┬───────┘
         │                       │
   height or -1           height or -1
         │                       │
         └──────────────┬────────┘
                        │
               if abs(L-R)>1 or L==-1 or R==-1
                        │
                      return -1
                        │
               else return 1 + max(L, R)

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: A balanced tree means both sides have the same number of nodes.

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 operations.

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

Common Belief: If the root's left and right subtrees are balanced, the whole tree is balanced.

Reality: Every node must satisfy the balance condition. Subtrees can be unbalanced even if root looks balanced.

Why it matters: Checking only the root misses imbalances deeper in the tree, causing incorrect results.

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

Common Belief: Calculating height separately for each node is efficient and fast.

Reality: Naive approach can be O(n^2) because height is recalculated many times.

Why it matters: Using naive method on large trees causes slow performance and timeouts.

Quick: Can the optimized balance check return height values other than -1 or positive integers? Commit yes or no.

Common Belief: The function returns only heights, no special values.

Reality: It uses -1 as a special signal to indicate imbalance, not a height.

Why it matters: Not understanding the special return value can cause bugs or incorrect logic.

Expert Zone

1

The early return of -1 not only signals imbalance but also prunes the recursion tree, saving time in large unbalanced trees.

2

Balance checking can be extended to other tree types by adjusting the height difference threshold, enabling flexible balancing criteria.

3

In some implementations, storing height in nodes can speed up repeated balance checks but requires careful updates on tree modifications.

When NOT to use

This balance check is not suitable for trees that allow more than two children per node or for trees where balance criteria differ, such as weight-balanced trees. For self-balancing trees like AVL or Red-Black trees, balance is maintained during insertions and deletions, so separate checks are less common.

Production Patterns

In production, this check is used during debugging or validation of tree structures. It is also foundational for implementing self-balancing trees that maintain balance automatically. Some systems use this check periodically to rebalance or restructure trees for performance.

Connections

AVL Trees

Builds-on

Understanding balance checking is essential to grasp how AVL trees maintain strict height balance after insertions and deletions.

Divide and Conquer Algorithms

Same pattern

The recursive height and balance check uses divide and conquer by solving subproblems on left and right subtrees and combining results.

Structural Engineering

Analogy in stability

Just like balanced trees ensure stability in data, structural engineers ensure buildings are balanced to avoid collapse, showing cross-domain importance of balance.

Common Pitfalls

#1 Recalculating height for each node separately causes slow performance.

Wrong approach:

int height(TreeNode* node) {
if (!node) return 0;
return 1 + max(height(node->left), height(node->right));
}

bool isBalanced(TreeNode* root) {
if (!root) return true;
int lh = height(root->left);
int rh = height(root->right);
if (abs(lh - rh) > 1) return false;
return isBalanced(root->left) && isBalanced(root->right);
}

Correct approach:

int checkHeight(TreeNode* root) {
if (!root) return 0;
int leftHeight = checkHeight(root->left);
if (leftHeight == -1) return -1;
int rightHeight = checkHeight(root->right);
if (rightHeight == -1) return -1;
if (abs(leftHeight - rightHeight) > 1) return -1;
return 1 + max(leftHeight, rightHeight);
}

bool isBalanced(TreeNode* root) {
return checkHeight(root) != -1;
}

Root cause:

Not combining height and balance checks causes repeated height calculations, leading to O(n^2) time.

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

Wrong approach:

bool isBalanced(TreeNode* root) {
int lh = height(root->left);
int rh = height(root->right);
return abs(lh - rh) <= 1;
}

Correct approach:

bool isBalanced(TreeNode* root) {
if (!root) return true;
int lh = height(root->left);
int rh = height(root->right);
if (abs(lh - rh) > 1) return false;
return isBalanced(root->left) && isBalanced(root->right);
}

Root cause:

Misunderstanding that balance must hold at every node, not just the root.

Key Takeaways

A binary tree is balanced if every node's left and right subtree heights differ by at most one.

Naive balance checks that compute height separately for each node are inefficient and can be O(n^2).

The optimized approach combines height calculation and balance checking in one recursive function for O(n) time.

Early detection of imbalance allows the function to stop checking further, saving time.

Understanding balance checking is foundational for learning self-balancing trees and maintaining efficient tree operations.

Practice

1. What does it mean for a binary tree to be balanced?

easy

A. All nodes have two children

B. The height difference between left and right subtrees of every node is at most 1

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

   Options B, C, and D describe other 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 B

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(TreeNode* root);

B. int isBalanced(TreeNode root);

C. void isBalanced(TreeNode* root);

D. bool isBalanced(TreeNode root);

Solution

1. Step 1: Identify correct parameter type

   The function should accept a pointer to the root node (TreeNode* root) to access the tree.

2. Step 2: Identify correct return type

   It should return bool to indicate if the tree is balanced or not.

3. Final Answer:

   bool isBalanced(TreeNode* root); -> Option A

4. Quick Check:

   Pointer parameter + bool return = correct signature [OK]

Hint: Use pointer parameter and bool return type [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Using int or void as return type
• Missing pointer symbol * in parameter

3. What will be the output of the following code snippet?

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

bool isBalanced(TreeNode* root) {
  if (!root) return true;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  if (abs(leftHeight - rightHeight) > 1) return false;
  return isBalanced(root->left) && isBalanced(root->right);
}

int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->left->left = new TreeNode(5);
  std::cout << (isBalanced(root) ? "Balanced" : "Not Balanced") << std::endl;
  return 0;
}

medium

A. Not Balanced

B. Balanced

C. Compilation Error

D. Runtime Error

Solution

1. Step 1: Calculate heights of subtrees

   Left subtree has height 3 (nodes 2->4->5), right subtree height is 1 (node 3).

2. Step 2: Check balance condition

   Height difference at root is 3 - 1 = 2, which is greater than 1, so tree is not balanced.

3. Final Answer:

   Not Balanced -> Option A

4. Quick Check:

   Height difference > 1 means Not Balanced [OK]

Hint: Check height difference > 1 means unbalanced [OK]

Common Mistakes:

• Ignoring height difference at root
• Assuming tree is balanced if only some nodes are balanced
• Confusing height with number of nodes

4. Identify the bug in this code snippet that checks if a binary tree is balanced:

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

bool isBalanced(TreeNode* root) {
  if (!root) return true;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  if (abs(leftHeight - rightHeight) > 1) return false;
  isBalanced(root->left);
  isBalanced(root->right);
  return true;
}

medium

A. Base case in height is incorrect

B. height function returns wrong height

C. abs function is not included

D. Missing return statements for recursive calls in isBalanced

Solution

1. Step 1: Analyze isBalanced recursive calls

   Recursive calls to isBalanced(root->left) and isBalanced(root->right) are made but their results are ignored.

2. Step 2: Fix missing return statements

   Must return the logical AND of these calls to correctly check balance in subtrees.

3. Final Answer:

   Missing return statements for recursive calls in isBalanced -> Option D

4. Quick Check:

   Recursive calls must return and combine results [OK]

Hint: Return recursive calls combined with && [OK]

Common Mistakes:

• Ignoring return values of recursive calls
• Returning true too early
• Incorrect base case handling

5. Given a binary tree, how can you optimize the balance check to avoid repeated height calculations?

hard

A. Use breadth-first traversal to check balance

B. Calculate height separately for left and right subtrees multiple times

C. Use a helper function that returns both height and balance status in one traversal

D. Check balance only at the root node

Solution

1. Step 1: Understand repeated height calculation problem

   Calculating height separately for each node causes repeated work and increases time complexity.

2. Step 2: Use combined helper function

   A helper function can return both height and balance status together, allowing one traversal to check balance efficiently.

3. Final Answer:

   Use a helper function that returns both height and balance status in one traversal -> Option C

4. Quick Check:

   Combine height and balance check in one pass [OK]

Hint: Combine height and balance check in one function [OK]

Common Mistakes:

• Calculating height multiple times causing O(n²) time
• Checking balance only at root misses subtree imbalance
• Using BFS does not directly help balance check