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↓

Check if left subtree balanced

↓

Check if right subtree balanced

↓

If both balanced, return True

No↓

Return False

We start from the root, check heights of left and right subtrees, compare their difference, and recursively verify if both subtrees are balanced.

Execution Sample

DSA C++

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);
}

This code checks if a binary tree is balanced by comparing subtree heights and recursively checking subtrees.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Difference	Balanced?	Tree State
1	Start at root	1	?	?	?	?	1 / \ 2 3
2	Check left subtree height	2	?	?	?	?	2 / \ 4 5
3	Check left subtree height	4	0	0	0	True	4
4	Check right subtree height	5	0	0	0	True	5
5	Compare heights at node 2	2	1	1	0	True	2 / \ 4 5
6	Check right subtree height	3	?	?	?	?	3 \ 6
7	Check left subtree height	null	0	0	0	True	null
8	Check right subtree height	6	0	0	0	True	6
9	Compare heights at node 3	3	0	1	1	True	3 \ 6
10	Compare heights at root	1	2	2	0	True	1 / \ 2 3
11	Check left subtree balanced	2	1	1	0	True	2 / \ 4 5
12	Check right subtree balanced	3	0	1	1	True	3 \ 6
13	Return final result	1	2	2	0	True	1 / \ 2 3
14	Exit	N/A	N/A	N/A	N/A	True	Balanced tree confirmed

💡 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	Node 1	Node 1	Node 1	Node 1	Node 1	Node 1
lh (left height)	?	1	1	0	2	2
rh (right height)	?	?	?	1	2	2
balanced	?	True	True	True	True	True

Key Moments - 3 Insights

Why do we check height difference at every node instead of only at the root?

Because a subtree can be unbalanced even if the root looks balanced. The execution_table rows 5, 9, and 10 show height differences checked at each node to ensure full balance.

What happens if a subtree is null (empty)?

A null subtree has height 0 and is considered balanced. Step 7 shows checking a null node returns height 0 and balanced True.

Why do we recursively check both left and right subtrees for balance?

Because both subtrees must be balanced for the whole tree to be balanced. Steps 11 and 12 show recursive balance checks on left and right subtrees.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the height difference at node 2?

A 0

B 1

C 2

D Undefined

💡 Hint

Check the 'Height Difference' column at step 5 in the execution_table.

At which step does the algorithm confirm the right subtree of node 3 is balanced?

A Step 7

B Step 9

C Step 8

D Step 12

💡 Hint

Look at the 'Balanced?' column and 'Node Visited' at step 8 in the execution_table.

If the height difference at the root was 3, what would be the balanced result at step 10?

A True

B False

C Depends on subtrees

D Cannot determine

💡 Hint

Recall the condition abs(lh - rh) > 1 returns false balance; see step 10 logic.

Concept Snapshot

Check if Binary Tree is Balanced:
- For each node, get left and right subtree heights
- If height difference > 1, tree is unbalanced
- Recursively check left and right subtrees
- Return true only if all nodes balanced
- Base case: null node is balanced with height 0

Full Transcript

To check if a binary tree is balanced, we start at the root node. We find the height of the left subtree and the right subtree. We compare their heights. If the difference is more than 1, the tree is not balanced. If the difference is 1 or less, we check recursively if the left subtree is balanced and if the right subtree is balanced. If both are balanced, the whole tree is balanced. If any subtree is not balanced, the whole tree is not balanced. A null subtree has height zero and is balanced by definition. This process continues until all nodes are checked or an imbalance is found.