Check if Binary Tree is Balanced in DSA Python - 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↓

Check left subtree balanced?

Yes↓

Check right subtree balanced?

Yes↓

Return True

↓

End

The flow checks heights of left and right subtrees recursively, compares their difference, and ensures both subtrees are balanced.

Execution Sample

DSA Python

def is_balanced(root):
    def check(node):
        if not node:
            return 0, True
        lh, lb = check(node.left)
        rh, rb = check(node.right)
        balanced = lb and rb and abs(lh - rh) <= 1
        return 1 + max(lh, rh), balanced
    return check(root)[1]

This code checks if a binary tree is balanced by recursively computing subtree heights and balance status.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Balanced Left	Balanced Right	Balanced Current	Return Height	Visual State
1	Check node 1	1	2	2	True	True	True	3	1(3)
2	Check node 2	2	1	1	True	True	True	2	2(2) -> 1(3)
3	Check node 4	4	0	0	True	True	True	1	4(1) -> 2(2) -> 1(3)
4	Check node 5	5	0	0	True	True	True	1	5(1) -> 2(2) -> 1(3)
5	Check node 3	3	1	1	True	True	True	2	3(2) -> 1(3)
6	Check node 6	6	0	0	True	True	True	1	6(1) -> 3(2) -> 1(3)
7	Check node 7	7	0	0	True	True	True	1	7(1) -> 3(2) -> 1(3)
8	Return final	1	-	-	-	-	True	-	Tree balanced with height 3

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

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
node	root (1)	4	3	7	None
left_height	-	0 (node 4)	1 (node 6)	0 (node 7)	-
right_height	-	0 (node 5)	1 (node 7)	0 (node 7)	-
balanced_left	-	True	True	True	-
balanced_right	-	True	True	True	-
balanced_current	-	-	True	True	True
return_height	-	1	2	1	3

Key Moments - 3 Insights

Why do we return both height and balance status together?

Returning both height and balance status at each step (see execution_table rows 1-7) avoids repeated height calculations and allows early detection of imbalance.

What happens if a subtree is None (empty)?

An empty subtree returns height 0 and balanced True immediately (see step 3 and 4), serving as the base case for recursion.

Why check abs(left_height - right_height) <= 1?

This condition ensures the current node's subtree is balanced; if difference is more than 1, the tree is unbalanced (see step 1 for example).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the balanced status of node 3?

A True

B False

C Unknown

D Depends on children

💡 Hint

Check the 'Balanced Current' column at step 5 in execution_table.

At which step does the function first return a height of 1?

A Step 1

B Step 5

C Step 3

D Step 8

💡 Hint

Look at the 'Return Height' column in execution_table for the earliest 1.

If the left subtree height was 3 and right subtree height was 1 at node 1, what would be the balanced status?

A True

B False

C Depends on other nodes

D Cannot determine

💡 Hint

Recall the condition abs(left_height - right_height) <= 1 from execution_table step 1.

Concept Snapshot

Check if Binary Tree is Balanced:
- Recursively get height and balance of left and right subtrees
- Balanced if both subtrees balanced and height difference ≤ 1
- Return combined height and balance status
- Base case: empty node returns height 0 and balanced True
- Final result is balance status of root

Full Transcript

This visualization shows how to check if a binary tree is balanced by recursively computing the height and balance status of each subtree. Starting from the root, the algorithm checks left and right subtree heights and balance. If the height difference is more than 1 or any subtree is unbalanced, it returns False. Otherwise, it returns True. The execution table traces each node visit, heights, and balance decisions. Key moments clarify why height and balance are returned together, the base case for empty nodes, and the importance of height difference condition. The quiz tests understanding of balance status at specific steps and the effect of height differences.

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