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.

Practice

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

easy

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

B. All nodes have two children

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 no node has left and right subtree heights differing by more than 1.

2. Step 2: Compare options

   The height difference between left and right subtrees of every node is at most 1 correctly states this condition. Other options describe different tree properties.

3. Final Answer:

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

4. Quick Check:

   Balance = 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 TypeScript function signature correctly represents a function to check if a binary tree is balanced?

easy

A. function isBalanced(root: number): boolean

B. function isBalanced(root: TreeNode | null): boolean

C. function isBalanced(root: TreeNode): number

D. function isBalanced(root: TreeNode | null): void

Solution

1. Step 1: Identify correct parameter and return types

   The function should accept a TreeNode or null and return a boolean indicating balance.

2. Step 2: Match options

   function isBalanced(root: TreeNode | null): boolean matches this signature. Others have wrong parameter types or return types.

3. Final Answer:

   function isBalanced(root: TreeNode | null): boolean -> Option B

4. Quick Check:

   Input: TreeNode|null, Output: boolean [OK]

Hint: Check input type is TreeNode|null and output is boolean [OK]

Common Mistakes:

• Using number as input instead of TreeNode
• Returning number instead of boolean
• Using void return type

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

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

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

function isBalanced(root: TreeNode | null): boolean {
  return checkHeight(root) !== -1;
}

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

console.log(isBalanced(root));

medium

A. true

B. Runtime error

C. undefined

D. false

Solution

1. Step 1: Analyze tree structure

   The tree is left-heavy: root.left.left.left exists but right subtree is shallow, causing imbalance.

2. Step 2: Trace checkHeight calls

   checkHeight returns -1 when height difference > 1, so isBalanced returns false.

3. Final Answer:

   false -> Option D

4. Quick Check:

   Left-heavy deep subtree -> not balanced -> false [OK]

Hint: Deep left subtree with shallow right subtree means unbalanced [OK]

Common Mistakes:

• Assuming tree is balanced without checking height difference
• Confusing return values of checkHeight
• Ignoring the -1 sentinel for imbalance

4. Identify the bug in this TypeScript function to check if a binary tree is balanced:

function isBalanced(root: TreeNode | null): boolean {
  if (!root) return true;
  const leftHeight = getHeight(root.left);
  const rightHeight = getHeight(root.right);
  if (Math.abs(leftHeight - rightHeight) > 1) return false;
  return isBalanced(root.left) && isBalanced(root.right);
}

function getHeight(node: TreeNode | null): number {
  if (!node) return 0;
  return Math.max(getHeight(node.left), getHeight(node.right));
}

medium

A. Math.abs is used incorrectly

B. isBalanced should return true if root is null

C. getHeight does not add 1 to height, causing incorrect height calculation

D. Recursive calls in isBalanced are missing

Solution

1. Step 1: Review getHeight function

   getHeight returns max height of children but misses adding 1 for current node.

2. Step 2: Understand impact on balance check

   Without adding 1, height is underestimated, causing wrong balance results.

3. Final Answer:

   getHeight does not add 1 to height, causing incorrect height calculation -> Option C

4. Quick Check:

   Height must include current node (+1) [OK]

Hint: Always add 1 in height calculation for current node [OK]

Common Mistakes:

• Forgetting to add 1 in height function
• Misusing Math.abs
• Missing base case for null root

5. Given a binary tree, how can you efficiently check if it is balanced without recalculating heights multiple times?

hard

A. Use a bottom-up approach returning height or -1 for imbalance in one traversal

B. Calculate height of left and right subtrees separately for each node

C. Use breadth-first traversal to check balance at each level

D. Store all node heights in a global array and compare after traversal

Solution

1. Step 1: Understand inefficiency of top-down approach

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

2. Step 2: Use bottom-up approach

   Return height if balanced, else -1 for imbalance, stopping early and using one traversal.

3. Final Answer:

   Use a bottom-up approach returning height or -1 for imbalance in one traversal -> Option A

4. Quick Check:

   Bottom-up single pass = efficient balance check [OK]

Hint: Return height or -1 in one pass to avoid repeated height calls [OK]

Common Mistakes:

• Recalculating heights multiple times causing slow code
• Using breadth-first traversal which doesn't help balance check
• Storing heights globally without efficient update