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

Start from the root, check heights of left and right subtrees, verify difference ≤ 1, then check if both subtrees are balanced.

Execution Sample

DSA Javascript

function isBalanced(root) {
  if (!root) return true;
  function height(node) {
    if (!node) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
  }
  const leftHeight = height(root.left);
  const rightHeight = height(root.right);
  if (Math.abs(leftHeight - rightHeight) > 1) return false;
  return isBalanced(root.left) && isBalanced(root.right);
}

Checks if a binary tree is balanced by comparing subtree heights and recursively verifying balance.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Difference	Balanced?	Visual State
1	Start at root	A	?	?	?	?	A / \ B C
2	Calculate left subtree height	B	1	1	?	?	A / \ B C / \ D E
3	Calculate right subtree height	C	0	0	?	?	A / \ B C / \ D E
4	Compare heights at A	A	2	1	1	Yes	A / \ B C / \ D E
5	Check if left subtree balanced	B	1	1	0	Yes	A / \ B C / \ D E
6	Check if right subtree balanced	C	0	0	0	Yes	A / \ B C / \ D E
7	Return final result	A	2	1	1	True	A / \ B C / \ D E

💡 All nodes checked, height differences ≤ 1, tree is balanced

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
currentNode	A	B	C	A	B	C	A
leftHeight	?	1	1	2	2	2	2
rightHeight	?	?	0	1	1	0	1
heightDifference	?	?	?	1	0	0	1
balanced	?	?	?	Yes	Yes	Yes	True

Key Moments - 3 Insights

Why do we calculate height for both left and right subtrees before checking balance?

Because the balance depends on the height difference between left and right subtrees (see steps 2, 3, and 4 in execution_table). We need both heights to compare.

Why do we recursively check if left and right subtrees are balanced after comparing heights?

Because even if the current node's left and right subtree heights differ by ≤1, their subtrees might be unbalanced. Steps 5 and 6 show these recursive checks.

What does it mean if height difference is greater than 1 at any node?

It means the tree is not balanced at that node, so the function returns false immediately (see step 4 where difference >1 would cause 'Balanced?' to be No).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the height difference at node A?

A 2

B 0

C 1

D 3

💡 Hint

Check the 'Height Difference' column at step 4 in execution_table

At which step do we confirm that the right subtree rooted at C is balanced?

A Step 3

B Step 6

C Step 4

D Step 7

💡 Hint

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

If the left subtree height at node B was 3 instead of 1, what would happen at step 4?

A Height difference would be greater than 1, so balanced would be false

B Height difference would still be 1, balanced true

C The function would skip checking right subtree

D The function would return true immediately

💡 Hint

Height difference is absolute difference of left and right heights; if left is 3 and right is 1, difference is 2 > 1

Concept Snapshot

Check if Binary Tree is Balanced:
- For each node, find 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
- Uses post-order traversal to compute heights

Full Transcript

This visualization shows how to check if a binary tree is balanced. We start at the root node and calculate the height of its left and right subtrees. The height is the longest path from a node down to a leaf. We compare these heights; if their difference is more than 1, the tree is not balanced. Then we recursively check if the left and right subtrees themselves are balanced. The execution table tracks each step, showing the node visited, heights calculated, and balance status. The variable tracker shows how key variables change during execution. Key moments clarify why we calculate heights first and why recursive checks are needed. The quiz tests understanding of height differences and balance checks. This method uses a post-order style traversal to ensure all nodes are checked for balance.

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 tree is a complete binary tree

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

Solution

1. Step 1: Understand balance condition

   A balanced binary tree means the height difference between left and right subtrees of every node is at most 1.

2. Step 2: Compare other options

   Options A, B, and D describe other tree properties but not the balance condition.

3. Final Answer:

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

4. Quick Check:

   Balance means height difference ≤ 1 [OK]

Hint: Balance means subtree heights differ by no more than 1 [OK]

Common Mistakes:

• Confusing balanced with complete tree
• Thinking balance means equal nodes on both sides
• Assuming all nodes must have two children

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

easy

A. function checkBalance(tree) { ... }

B. function isBalanced(root) { ... }

C. function balancedCheck(node) { ... }

D. function isBalancedTree() { ... }

Solution

1. Step 1: Identify common parameter for tree root

   The function should accept the root node as a parameter to check balance.

2. Step 2: Check function signatures

   Only function isBalanced(root) { ... } uses a clear parameter named 'root' which is standard for tree root nodes.

3. Final Answer:

   function isBalanced(root) { ... } -> Option B

4. Quick Check:

   Function needs root parameter [OK]

Hint: Function must accept root node parameter [OK]

Common Mistakes:

• Omitting root parameter
• Using unclear or no parameters
• Using function names that don't indicate balance check

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

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function height(node) {
  if (!node) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

function isBalanced(root) {
  if (!root) return true;
  let leftHeight = height(root.left);
  let rightHeight = height(root.right);
  if (Math.abs(leftHeight - rightHeight) > 1) return false;
  return isBalanced(root.left) && isBalanced(root.right);
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.left.left = new Node(5);

console.log(isBalanced(root));

medium

A. false

B. true

C. undefined

D. Throws error

Solution

1. Step 1: Calculate heights of left and right subtrees

   Left subtree height is 3 (nodes 2 -> 4 -> 5), right subtree height is 1 (node 3).

2. Step 2: Check balance condition at root

   Height difference is 3 - 1 = 2, which is greater than 1, so tree is not balanced.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Height difference > 1 means not balanced [OK]

Hint: Check height difference > 1 returns false [OK]

Common Mistakes:

• Ignoring deeper subtree height
• Assuming tree is balanced if root has two children
• Confusing height with number of nodes

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

function isBalanced(root) {
  if (!root) return true;
  let leftHeight = height(root.left);
  let rightHeight = height(root.right);
  if (Math.abs(leftHeight - rightHeight) > 1) return false;
  isBalanced(root.left);
  isBalanced(root.right);
  return true;
}

medium

A. Height function is not defined

B. Incorrect base case for empty tree

C. Missing return statements for recursive calls

D. Using Math.abs incorrectly

Solution

1. Step 1: Analyze recursive calls

   The calls to isBalanced(root.left) and isBalanced(root.right) are made but their results are not returned or checked.

2. Step 2: Identify missing return usage

   Without returning these recursive calls, the function always returns true after checking root, ignoring subtree balance.

3. Final Answer:

   Missing return statements for recursive calls -> Option C

4. Quick Check:

   Recursive calls must return their results [OK]

Hint: Always return recursive call results [OK]

Common Mistakes:

• Not returning recursive call results
• Assuming base case covers all
• Ignoring subtree balance checks

5. Given a binary tree, which approach is the most efficient to check if it is balanced without recalculating heights multiple times?

hard

A. Use a bottom-up recursion that returns height and balance status together

B. Check balance only at the root node

C. Traverse the tree level by level and count nodes

D. Calculate height for each node separately and check balance

Solution

1. Step 1: Understand inefficiency of separate height calculations

   Calculating height separately for each node causes repeated work, increasing time complexity.

2. Step 2: Use bottom-up recursion

   Returning height and balance status together in one recursion avoids repeated height calculations, improving efficiency.

3. Final Answer:

   Use a bottom-up recursion that returns height and balance status together -> Option A

4. Quick Check:

   Bottom-up recursion avoids repeated height calls [OK]

Hint: Combine height and balance in one recursion [OK]

Common Mistakes:

• Recalculating heights multiple times
• Checking balance only at root
• Using level order traversal for balance