Check if Binary Tree is Balanced in DSA Python - 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. Checking if a binary tree is balanced helps ensure operations like search, insert, and delete run efficiently. It is a common problem in computer science to maintain good performance in tree structures.

Why it matters

Without checking balance, a binary tree can become very uneven, like a tall skinny tree, making operations slow and inefficient. This can cause programs to lag or use more resources. Balanced trees keep data organized so computers can find and update information quickly, which is important in databases, file systems, and many applications.

Where it fits

Before this, you should understand what a binary tree is and how to measure its height. After learning this, you can explore 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 subtree heights differ by more than one.

Think of it like...

Imagine a seesaw with two kids sitting on each side. The seesaw is balanced if both kids are roughly the same weight, so it stays level and doesn't tip too far to one side.

       Root
      /    \
   Left   Right
   Subtree Subtree

Height difference ≤ 1 means balanced

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 0. We use recursion to find height: if node is None, height is -1; else height = 1 + max(height(left), height(right)).

Result

You can calculate the height of any node in the 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: the height difference between left and right subtrees of every node must be at most one.

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

Result

You understand the exact condition that makes a tree 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, call a function to get left height and right height, then check difference. Recursively check balance for left and right children. This approach is simple but repeats height calculations many times.

Result

You can determine if a tree is balanced but with repeated work causing inefficiency.

This method works but wastes time recalculating heights, leading to slow performance on large trees.

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 two things: the height of the subtree and whether it is balanced. For each node, recursively get left and right results. If either subtree is unbalanced or height difference > 1, mark current subtree unbalanced. Otherwise, return height and balanced status.

Result

You can check balance in O(n) time by visiting each node once.

Merging height and balance checks prevents repeated height calculations, making the algorithm efficient.

5

Advanced

Implementing the Optimized Balance Check in Python

🤔Before reading on: predict the output of the code when given a balanced and an unbalanced tree. Commit to your answer.

Concept: Use recursion with a helper function returning height and balance status to implement the check.

```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def is_balanced(root): def check(node): if not node: return -1, True left_height, left_balanced = check(node.left) right_height, right_balanced = check(node.right) current_balanced = ( left_balanced and right_balanced and abs(left_height - right_height) <= 1 ) current_height = 1 + max(left_height, right_height) return current_height, current_balanced _, balanced = check(root) return balanced # Example usage: # Balanced tree root_balanced = TreeNode(1, TreeNode(2), TreeNode(3)) print(is_balanced(root_balanced)) # Output: True # Unbalanced tree root_unbalanced = TreeNode(1, TreeNode(2, TreeNode(3)), None) print(is_balanced(root_unbalanced)) # Output: False ```

Result

True False

This code efficiently checks balance by returning height and balance status together, avoiding repeated height calls.

6

Expert

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: Consider recursion limits and edge cases like empty trees or skewed trees in production.

Empty trees are balanced by definition. Very deep trees may cause stack overflow in recursion. Iterative approaches or increasing recursion limits can help. Also, understanding that balance checking is a key step before applying self-balancing tree algorithms is important.

Result

You know how to handle special cases and limitations in real systems.

Recognizing recursion limits and edge cases prevents runtime errors and improves robustness in real applications.

Under the Hood

The algorithm uses recursion to explore each node's left and right children. At each node, it calculates the height of subtrees and checks their balance status. By returning both height and balance status together, it avoids recalculating heights multiple times. The recursion unwinds from leaves to root, combining results to determine overall balance.

Why designed this way?

Early naive methods recalculated heights repeatedly, causing slow performance. The combined approach was designed to optimize time complexity to linear, O(n), by visiting each node once. This design balances simplicity and efficiency, making it practical for large trees.

          check(node)
             │
    ┌────────┴────────┐
check(left)        check(right)
    │                  │
(height, balanced) (height, balanced)
    │                  │
    └─────combine results─────┐
             │               │
      calculate height   check balance
             │               │
         return (height, balanced)

Myth Busters - 3 Common Misconceptions

Quick: Is a tree with height difference 2 at one node still balanced? Commit yes or no.

Common Belief: A tree is balanced as long as the overall height difference between left and right subtrees of the root is small.

Reality: Balance must hold at every node, not just the root. Even one node with height difference greater than 1 makes the tree unbalanced.

Why it matters: Ignoring local imbalance can cause algorithms to assume efficiency incorrectly, leading to slow operations.

Quick: Does checking balance by computing height separately for each node run in linear time? Commit yes or no.

Common Belief: Calculating height separately for each node is efficient enough for balance checking.

Reality: This approach is inefficient and can take O(n^2) time in worst cases because height is recalculated many times.

Why it matters: Using inefficient methods can cause programs to slow down drastically on large trees.

Quick: Can an empty tree be considered unbalanced? Commit yes or no.

Common Belief: An empty tree is not balanced because it has no nodes.

Reality: An empty tree is balanced by definition since there are no nodes to violate balance conditions.

Why it matters: Misunderstanding this can cause unnecessary errors or checks in code.

Expert Zone

1

The combined height and balance check function returns a tuple to avoid global variables and keep recursion clean.

2

In some languages or environments, tail recursion optimization can improve performance, but Python does not support it natively.

3

Balance checking is a prerequisite for many self-balancing tree algorithms, which maintain balance during insertions and deletions.

When NOT to use

This check is not suitable for trees that allow more than two children per node (non-binary trees). For those, different balance definitions and checks apply. Also, for very large or deep trees, iterative or stack-based methods may be preferred to avoid recursion limits.

Production Patterns

In production, balance checks are often integrated into tree update operations to maintain balance incrementally. For example, AVL trees perform rotations during insert/delete to keep balance without full checks. Balance checking is also used in debugging and validating tree structures.

Connections

AVL Trees

Builds-on

Understanding balance checking is essential to grasp how AVL trees maintain strict balance after every update.

Recursion

Same pattern

The recursive pattern of combining results from subproblems is a common technique in many algorithms beyond trees.

Structural Engineering

Analogous principle

Just like balanced trees in computing, buildings must be balanced structurally to avoid collapse, showing how balance concepts cross disciplines.

Common Pitfalls

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

Wrong approach:

def height(node):
if not node:
return -1
return 1 + max(height(node.left), height(node.right))

def is_balanced(node):
if not node:
return True
left_height = height(node.left)
right_height = height(node.right)
if abs(left_height - right_height) > 1:
return False
return is_balanced(node.left) and is_balanced(node.right)

Correct approach:

def check(node):
if not node:
return -1, True
left_height, left_balanced = check(node.left)
right_height, right_balanced = check(node.right)
balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
return 1 + max(left_height, right_height), balanced

def is_balanced(root):
_, balanced = check(root)
return balanced

Root cause:

Not combining height and balance checks leads to repeated height calculations and inefficiency.

#2 Assuming only the root node's height difference matters for balance.

Wrong approach:

def is_balanced(root):
left_height = height(root.left)
right_height = height(root.right)
return abs(left_height - right_height) <= 1

Correct approach:

def check(node):
if not node:
return -1, True
left_height, left_balanced = check(node.left)
right_height, right_balanced = check(node.right)
balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
return 1 + max(left_height, right_height), balanced

def is_balanced(root):
_, balanced = check(root)
return balanced

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 no more than one.

Checking balance efficiently requires combining height calculation and balance verification in one recursive pass.

Naive methods that calculate height repeatedly for each node lead to slow, quadratic time complexity.

Balanced trees ensure faster operations like search and insert by preventing skewed structures.

Understanding balance checking is foundational for learning self-balancing trees used in real-world systems.

Practice

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

easy

A. The tree has the same number of nodes on left and right

B. All nodes have two children

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

D. The tree is a complete binary tree

Solution

1. Step 1: Understand the balance condition

   A balanced binary tree means for every node, the height difference between its left and right subtree is at most 1.

2. Step 2: Compare options with definition

   The height difference between left and right subtrees of every node is at most 1 matches this definition exactly, while others describe different tree properties.

3. Final Answer:

   The height difference between left and right subtrees of every node is at most 1 -> Option C

4. Quick Check:

   Balanced tree = height difference ≤ 1 [OK]

Hint: Balance means height difference ≤ 1 at every node [OK]

Common Mistakes:

• Confusing balanced with complete tree
• Thinking balanced means equal number of nodes
• Assuming all nodes must have two children

2. Which of the following Python function signatures is correct to check if a binary tree is balanced?

easy

A. def is_balanced(root: List[int]) -> bool:

B. def is_balanced(root: int) -> int:

C. def is_balanced(tree: str) -> bool:

D. def is_balanced(root: Optional[TreeNode]) -> bool:

Solution

1. Step 1: Identify correct parameter type for binary tree root

   The root of a binary tree is typically a TreeNode or None, so Optional[TreeNode] is correct.

2. Step 2: Check return type for balance check

   The function should return a boolean indicating if the tree is balanced, so return type bool is correct.

3. Final Answer:

   def is_balanced(root: Optional[TreeNode]) -> bool: -> Option D

4. Quick Check:

   Function signature matches tree root and bool return [OK]

Hint: Use TreeNode or Optional[TreeNode] as input, bool as output [OK]

Common Mistakes:

• Using int or str as input instead of TreeNode
• Returning int instead of bool
• Using list instead of tree node

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def check_height(node):
    if not node:
        return 0
    left_height = check_height(node.left)
    right_height = check_height(node.right)
    if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
        return -1
    return max(left_height, right_height) + 1

def is_balanced(root):
    return check_height(root) != -1

root = TreeNode(1, TreeNode(2, TreeNode(3)), TreeNode(4))
print(is_balanced(root))

medium

A. Runtime Error

B. True

C. None

D. False

Solution

1. Step 1: Analyze tree structure

   The tree root has left child 2 with left child 3, and right child 4. Left subtree height is 2, right subtree height is 1.

2. Step 2: Check balance condition

   At root, height difference is abs(2 - 1) = 1, which is allowed. But node 2 has left child 3 and no right child, so difference is abs(1 - 0) = 1, allowed. So tree is balanced.

3. Step 3: Re-examine code logic

   Wait, the code returns -1 if difference > 1. Here difference never exceeds 1, so check_height returns height, is_balanced returns True.

4. Step 4: Re-examine the tree carefully

   Node 2 has left child 3 (height 1) and no right child (height 0), difference is 1 (allowed). Root has left subtree height 2, right subtree height 1, difference 1 (allowed). So tree is balanced.

5. Final Answer:

   True -> Option B

6. Quick Check:

   Height difference ≤ 1 means balanced = True [OK]

Hint: Check height difference at each node; -1 means unbalanced [OK]

Common Mistakes:

• Miscounting subtree heights
• Confusing -1 return as False directly
• Ignoring base case for None nodes

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

def is_balanced(root):
    def height(node):
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        if abs(left - right) > 1:
            return False
        return max(left, right) + 1
    return height(root) != False

medium

A. Returning False instead of -1 breaks height calculation

B. Using != False instead of is not False causes error

C. Missing base case for leaf nodes

D. Not checking left and right subtree balance separately

Solution

1. Step 1: Understand return values in height function

   The height function returns integer heights, but returns False when unbalanced, mixing types.

2. Step 2: Identify impact on recursion

   Returning False breaks max(left, right) + 1 calculation because max expects integers, causing errors or wrong results.

3. Final Answer:

   Returning False instead of -1 breaks height calculation -> Option A

4. Quick Check:

   Use -1 for unbalanced, not False [OK]

Hint: Use -1 for unbalanced, not False, to keep height numeric [OK]

Common Mistakes:

• Mixing boolean and integer return types
• Incorrect final check with != False
• Not propagating unbalanced signal properly

5. Given a binary tree, which approach efficiently checks if it is balanced without recalculating heights multiple times?

hard

A. Use a bottom-up recursion returning height or -1 if unbalanced

B. Calculate height for each node separately, then check balance

C. Traverse tree twice: once for height, once for balance

D. Use breadth-first search to check balance at each level

Solution

1. Step 1: Understand naive approach drawbacks

   Calculating height separately for each node causes repeated work, leading to O(n²) time.

2. Step 2: Identify efficient approach

   Bottom-up recursion returns height if balanced, or -1 if unbalanced, stopping early and avoiding repeated height calculations.

3. Step 3: Compare other options

   Options B and C cause repeated calculations; D (BFS) does not directly check subtree heights efficiently.

4. Final Answer:

   Use a bottom-up recursion returning height or -1 if unbalanced -> Option A

5. Quick Check:

   Bottom-up recursion = efficient balance check [OK]

Hint: Return -1 early in recursion to avoid repeated height checks [OK]

Common Mistakes:

• Using top-down approach causing repeated height calls
• Trying BFS which doesn't check subtree heights easily
• Checking balance after separate height computations