Check if Binary Tree is Balanced in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of balance check on a simple tree

What is the output of the following TypeScript code that checks if a binary tree is balanced?

DSA Typescript

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

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

const tree = new TreeNode(1, new TreeNode(2, new TreeNode(3), null), null);
console.log(isBalanced(tree));

A false

B true

C SyntaxError

D TypeError

💡 Hint

Think about the height difference between left and right subtrees at each node.

The tree has root 1 with left child 2 and left child's left child 3. The right subtree is empty. The height difference at node 1 is 2 (left) vs 0 (right), which is more than 1, so the tree is not balanced. But let's check carefully.

Actually, the left subtree height is 2, right subtree height is 0, difference is 2 > 1, so the function returns false.

But the code returns true, so let's verify the code logic.

The code returns true if height is not -1. The height function returns -1 if difference > 1.

At node 2, left height is 1, right height is 0, difference 1 ≤ 1, so height is 2.

At root 1, left height 2, right height 0, difference 2 > 1, so height returns -1, so isBalanced returns false.

Therefore, the correct output is false.

❓ Predict Output

intermediate

Output of balance check on a balanced tree

What is the output of the following TypeScript code that checks if a binary tree is balanced?

DSA Typescript

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

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

const tree = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(isBalanced(tree));

A true

B false

C SyntaxError

D TypeError

💡 Hint

Check the height difference between left and right children of the root.

The tree has root 1 with left child 2 and right child 3. Both children are leaves.

The height difference at root is 1 vs 1, difference 0 ≤ 1, so balanced.

The function returns true.

🔧 Debug

advanced

Identify the error in balance check function

What error does the following TypeScript code produce when checking if a binary tree is balanced?

DSA Typescript

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

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

const tree = new TreeNode(1);
console.log(isBalanced(tree));

A No error, outputs true

B No error, outputs false

C Logical error, returns wrong result

D Runtime error due to incorrect order of checks

💡 Hint

Check the order of conditions that return -1 in the height function.

The height function checks the height difference before checking if leftHeight or rightHeight is -1.

If leftHeight or rightHeight is -1, it means subtree is unbalanced, so it should return -1 immediately.

But here, difference is checked first, which can cause wrong behavior or runtime error if leftHeight or rightHeight is -1.

This causes a logical error or runtime error.

🧠 Conceptual

advanced

Understanding balance condition in binary trees

Which of the following best describes the condition for a binary tree to be balanced?

A Every node's left and right subtrees have the same number of nodes

B For every node, the height difference between left and right subtrees is at most 1

C The tree has the minimum possible height for the number of nodes

D All leaf nodes are at the same depth

💡 Hint

Balance depends on height difference, not node count or leaf depth equality.

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

Equal number of nodes or all leaves at same depth are stricter conditions (perfect or complete trees).

🚀 Application

expert

Result of balance check after tree modification

Given the following TypeScript code that builds a binary tree and checks if it is balanced, what is the output after adding a new node to the leftmost leaf?

DSA Typescript

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

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

const leaf = new TreeNode(4);
const leftChild = new TreeNode(2, leaf, null);
const rightChild = new TreeNode(3);
const root = new TreeNode(1, leftChild, rightChild);

// Add new node to leftmost leaf
leaf.left = new TreeNode(5);

console.log(isBalanced(root));

A SyntaxError

B true

C false

D TypeError

💡 Hint

Adding a node to the leftmost leaf increases the height of left subtree by 2 levels.

Initially, the tree is balanced.

After adding a new node as left child of leaf (node 4), the left subtree height increases.

At root, left subtree height becomes 3, right subtree height is 1, difference 2 > 1.

Therefore, the tree is no longer balanced and function returns false.

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