Check if Binary Tree is Balanced in DSA Typescript - Execution Trace

Concept Flow - Check if Binary Tree is Balanced

Start at root node

↓

Check left subtree height

↓

Check right subtree height

↓

Compare heights difference <= 1?

Yes No↓

Check left balanced?

↓

Check right balanced?

↓

Return true if both balanced

The process checks heights of left and right subtrees at each node, ensuring difference is at most 1 and both subtrees are balanced.

Execution Sample

DSA Typescript

function isBalanced(root: TreeNode | null): boolean {
  function height(node: TreeNode | null): number {
    if (!node) return 0;
    const left = height(node.left);
    const right = height(node.right);
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
  }
  return height(root) !== -1;
}

This code checks if a binary tree is balanced by recursively computing subtree heights and returning -1 if imbalance is found.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Returned	Balanced Status	Tree State
1	Start at root	A	-	-	-	Unknown	A ├─ B │ ├─ D │ └─ E └─ C
2	Check left subtree	B	-	-	-	Unknown	Same as above
3	Check left subtree	D	-	-	-	Unknown	Same as above
4	Left child null	null	0	0	0	Balanced	Same as above
5	Right child null	null	0	0	0	Balanced	Same as above
6	Calculate height D	D	0	0	1	Balanced	Same as above
7	Check right subtree	E	-	-	-	Unknown	Same as above
8	Left child null	null	0	0	0	Balanced	Same as above
9	Right child null	null	0	0	0	Balanced	Same as above
10	Calculate height E	E	0	0	1	Balanced	Same as above
11	Calculate height B	B	1	1	2	Balanced	Same as above
12	Check right subtree	C	-	-	-	Unknown	Same as above
13	Left child null	null	0	0	0	Balanced	Same as above
14	Right child null	null	0	0	0	Balanced	Same as above
15	Calculate height C	C	0	0	1	Balanced	Same as above
16	Calculate height A	A	2	1	3	Balanced	Same as above
17	Return final result	A	2	1	3	Balanced	Tree is balanced

💡 Traversal ends after checking all nodes; no imbalance found, so tree is balanced.

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 15	After Step 16	Final
node	A	D	B	C	A	null
left height	-	0	1	0	2	-
right height	-	0	1	0	1	-
height returned	-	1	2	1	3	-
balanced status	Unknown	Balanced	Balanced	Balanced	Balanced	Balanced

Key Moments - 3 Insights

Why do we return -1 when imbalance is detected?

Returning -1 signals imbalance immediately, stopping further checks. See steps 6 and 16 where heights are compared; if difference >1, -1 is returned to propagate failure.

Why do we check left and right subtree heights before deciding balanced status?

Because balance depends on both subtrees being balanced and their heights differing by at most 1. Steps 4-10 show recursive height checks before final decision at step 16.

What happens if a node is null?

Null nodes return height 0 (steps 4,5,8,9,13,14), which is the base case for recursion and means empty subtree is balanced.

Visual Quiz - 3 Questions

Look at the execution table at step 11, what is the height returned for node B?

A 1

B 2

C 3

D -1

💡 Hint

Check the 'Height Returned' column at step 11 in the execution_table.

At which step does the algorithm confirm the tree is balanced?

A Step 6

B Step 11

C Step 16

D Step 17

💡 Hint

Look at the 'Balanced Status' and 'Return final result' in the execution_table.

If the right subtree of node A had height 0 instead of 1, what would be the height returned at step 16?

A 2

B 3

C -1

D 1

💡 Hint

Height at step 16 is max(left height, right height) + 1; check variable_tracker for heights.

Concept Snapshot

Check if Binary Tree is Balanced:
- Recursively find height of left and right subtrees
- If height difference > 1, return -1 (unbalanced)
- If any subtree returns -1, propagate -1 up
- If root returns -1, tree is unbalanced
- Otherwise, tree is balanced

Full Transcript

This visualization shows how to check if a binary tree is balanced by recursively computing the height of each subtree. Starting from the root, the algorithm checks left and right subtree heights. If the difference is more than 1, it returns -1 to indicate imbalance. Null nodes return height 0. The process continues until all nodes are checked or imbalance is found. The execution table tracks each node visited, heights computed, and balanced status. The variable tracker shows how heights and nodes change during recursion. Key moments clarify why -1 is used and how null nodes are handled. The quiz tests understanding of height values and final balanced result.