Check if Binary Tree is Balanced in DSA Typescript

Mental Model

A balanced binary tree means no branch is much longer than another. We check if every node's left and right branches differ in height by at most one.

Analogy: Imagine a tree with branches. If one branch is much longer than its sibling, the tree looks lopsided and might fall. We want to make sure all branches grow evenly.

      1
     / \
    2   3
   / 
  4  

Balanced tree example: left and right heights differ by at most 1.

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2, right child 3; 2 has left child 4

Goal: Determine if the tree is balanced by checking height differences at each node

Step 1: Check height of node 4 (leaf)

Node 4 height = 0 (no children)

Why: Leaf nodes have height 0, base case for height calculation

Step 2: Check height of node 2: left height = 0 (node 4), right height = -1 (no right child)

Height difference at node 2 = 1 (0 - (-1))

Why: Difference 1 is allowed, so node 2 is balanced

Step 3: Check height of node 3 (leaf)

Node 3 height = 0

Why: Leaf node height is 0

Step 4: Check height of root node 1: left height = 1 (node 2), right height = 0 (node 3)

Height difference at node 1 = 1 (1 - 0)

Why: Difference 1 is allowed, so root is balanced

Step 5: Since all nodes are balanced, return true

Tree is balanced

Why: No node violates the height difference rule

Result:

1
/ \
2   3
/ 
4

Balanced: true

Annotated Code

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 checkHeight(node: TreeNode | null): number {
    if (node === null) return -1; // base case: empty subtree height

    const leftHeight = checkHeight(node.left); // get left subtree height
    if (leftHeight === Number.MIN_SAFE_INTEGER) return Number.MIN_SAFE_INTEGER; // left subtree unbalanced

    const rightHeight = checkHeight(node.right); // get right subtree height
    if (rightHeight === Number.MIN_SAFE_INTEGER) return Number.MIN_SAFE_INTEGER; // right subtree unbalanced

    if (Math.abs(leftHeight - rightHeight) > 1) return Number.MIN_SAFE_INTEGER; // current node unbalanced

    return Math.max(leftHeight, rightHeight) + 1; // height of current node
  }

  return checkHeight(root) !== Number.MIN_SAFE_INTEGER;
}

// Driver code
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), null),
  new TreeNode(3)
);

console.log(isBalanced(root));

if (node === null) return -1; // base case: empty subtree height

return -1 height for empty subtree to count edges correctly

const leftHeight = checkHeight(node.left);

recursively get left subtree height

if (leftHeight === Number.MIN_SAFE_INTEGER) return Number.MIN_SAFE_INTEGER;

propagate unbalanced signal up if left subtree unbalanced

const rightHeight = checkHeight(node.right);

recursively get right subtree height

if (rightHeight === Number.MIN_SAFE_INTEGER) return Number.MIN_SAFE_INTEGER;

propagate unbalanced signal up if right subtree unbalanced

if (Math.abs(leftHeight - rightHeight) > 1) return Number.MIN_SAFE_INTEGER;

detect unbalanced node by height difference > 1

return Math.max(leftHeight, rightHeight) + 1;

return height of current node as max child height + 1

return checkHeight(root) !== Number.MIN_SAFE_INTEGER;

final check: if unbalanced signal not found, tree is balanced

Output

true

Complexity Analysis

Time: O(n) because we visit each node once to calculate heights and check balance

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach recalculates heights repeatedly causing O(n^2) time; this method calculates height and balance in one pass for O(n) time

Edge Cases

Empty tree (root is null)

Returns true because empty tree is balanced

DSA Typescript

if (node === null) return -1;

Single node tree

Returns true because single node has no imbalance

DSA Typescript

if (node === null) return -1;

Unbalanced tree with one branch much deeper

Returns false when height difference > 1 detected

DSA Typescript

if (Math.abs(leftHeight - rightHeight) > 1) return Number.MIN_SAFE_INTEGER;

When to Use This Pattern

When you need to check if a tree is balanced, use a bottom-up height check with early stopping to detect imbalance efficiently.

Common Mistakes

Mistake: Calculating height separately from balance check causing repeated work
Fix: Combine height calculation and balance check in one recursive function with early return

Mistake: Returning 0 for null nodes instead of -1, causing off-by-one height errors
Fix: Return -1 for null nodes to count edges correctly in height

Summary

Checks if a binary tree is balanced by ensuring height difference between left and right subtrees is at most one at every node.

Use when you want to verify tree balance to optimize operations like search or insert.

The key insight is to calculate height and check balance in one pass, returning a special value to stop early if unbalanced.

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