Check if Binary Tree is Balanced in DSA Typescript - Build from Scratch

Check if Binary Tree is Balanced

📖 Scenario: You are working on a program that manages a binary tree structure. A balanced binary tree is one where the difference in height between the left and right subtrees of every node is at most 1. This helps keep operations efficient.Imagine you want to check if your tree is balanced to ensure fast searching and insertion.

🎯 Goal: Build a TypeScript program that creates a binary tree, sets up a helper function to check balance, implements the logic to verify if the tree is balanced, and finally prints the result.

📋 What You'll Learn

Create a binary tree node class called TreeNode with val, left, and right properties

Create a sample binary tree with exact nodes and structure

Create a helper function called checkHeight that returns the height of a subtree or -1 if unbalanced

Create a function called isBalanced that uses checkHeight to determine if the tree is balanced

Print true or false depending on whether the tree is balanced

💡 Why This Matters

🌍 Real World

Balanced binary trees are used in databases and file systems to keep data organized for fast searching and updating.

💼 Career

Understanding tree balance is important for software engineers working on performance-critical applications and data structure optimization.

1

Create the Binary Tree Structure

Create a class called TreeNode with a constructor that takes a number val and initializes left and right as null. Then create a binary tree with root node value 1, left child 2, and right child 3. The left child 2 should have a left child 4 and right child 5. The right child 3 should have no children.

DSA Typescript

// Define TreeNode class and create the binary tree
// Your code here

Hint

Start by defining the TreeNode class with the required properties. Then create the nodes exactly as described and link them.

2

Create the Helper Function to Check Height

Create a function called checkHeight that takes a TreeNode | null parameter called node. It should return -1 if the subtree is unbalanced. Otherwise, it returns the height of the subtree. Use recursion to get the left and right subtree heights, and if their difference is more than 1, return -1.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

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

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

// Create checkHeight function below
// Your code here

Hint

Use recursion to get heights of left and right subtrees. Return -1 if unbalanced at any point.

3

Create the Function to Check if Tree is Balanced

Create a function called isBalanced that takes a TreeNode | null parameter called root. It should return true if the tree is balanced and false otherwise. Use the checkHeight function inside it and check if the result is not -1.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

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

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

function checkHeight(node: TreeNode | null): number {
    if (node === null) {
        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;
}

// Create isBalanced function below
// Your code here

Hint

Use the checkHeight function and return true if it does not return -1.

4

Print if the Tree is Balanced

Write a console.log statement to print the result of calling isBalanced with the root node.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

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

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

function checkHeight(node: TreeNode | null): number {
    if (node === null) {
        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;
}

// Print the result below
// Your code here

Hint

Call isBalanced(root) and print the result using console.log.

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