Check if Binary Tree is Balanced in DSA Javascript

Mental Model

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

Analogy: Imagine a tree with branches on both sides. If one side is much taller than the other, the tree might lean or fall. A balanced tree stands straight because both sides grow evenly.

      1
     / \
    2   3
   /     \
  4       5

Dry Run Walkthrough

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

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

Step 1: Check leaf node 4: left and right heights are 0

Node 4: height=1, balanced=true

Why: Leaf nodes have height 1 and are balanced by definition

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

Node 2: height=2, balanced=true (difference 1)

Why: Height difference is 1, so node 2 is balanced

Step 3: Check leaf node 5: left and right heights are 0

Node 5: height=1, balanced=true

Why: Leaf nodes have height 1 and are balanced

Step 4: Check node 3: left height=0, right height=1 (from 5)

Node 3: height=2, balanced=true (difference 1)

Why: Height difference is 1, so node 3 is balanced

Step 5: Check root node 1: left height=2 (from 2), right height=2 (from 3)

Node 1: height=3, balanced=true (difference 0)

Why: Height difference is 0, so root is balanced

Result:

1 (height=3, balanced) -> 2 (height=2, balanced) -> 3 (height=2, balanced) -> 4 (height=1, balanced) -> 5 (height=1, balanced)
Final answer: Tree is balanced

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isBalanced(root) {
  // Returns [height, balanced] for subtree rooted at node
  function check(node) {
    if (node === null) return [0, true];

    const [leftHeight, leftBalanced] = check(node.left); // check left subtree
    const [rightHeight, rightBalanced] = check(node.right); // check right subtree

    const height = Math.max(leftHeight, rightHeight) + 1; // current node height
    const balanced = leftBalanced && rightBalanced && Math.abs(leftHeight - rightHeight) <= 1; // balanced if subtrees balanced and height diff <=1

    return [height, balanced];
  }

  return check(root)[1];
}

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

console.log(isBalanced(root) ? "Tree is balanced" : "Tree is not balanced");

if (node === null) return [0, true];

base case: empty subtree has height 0 and is balanced

const [leftHeight, leftBalanced] = check(node.left);

recursively check left subtree height and balance

const [rightHeight, rightBalanced] = check(node.right);

recursively check right subtree height and balance

const height = Math.max(leftHeight, rightHeight) + 1;

calculate current node height as max of children plus one

const balanced = leftBalanced && rightBalanced && Math.abs(leftHeight - rightHeight) <= 1;

node is balanced if both subtrees balanced and height difference ≤ 1

return [height, balanced];

return height and balance status up the recursion

return check(root)[1];

final answer is balance status of entire tree

Output

Tree is balanced

Complexity Analysis

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

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

vs Alternative: Naive approach checks height separately for each node causing O(n^2) time; this method combines height and balance check in one pass for O(n) time

Edge Cases

Empty tree (root is null)

Returns true because empty tree is balanced

DSA Javascript

if (node === null) return [0, true];

Single node tree

Returns true because single node is balanced

DSA Javascript

if (node === null) return [0, true];

Tree with one side deeper by more than 1

Returns false because height difference > 1 at some node

DSA Javascript

const balanced = leftBalanced && rightBalanced && Math.abs(leftHeight - rightHeight) <= 1;

When to Use This Pattern

When a problem asks if a tree is balanced or height differences matter, use a bottom-up recursion that returns height and balance status together to avoid repeated height calculations.

Common Mistakes

Mistake: Calculating height separately for each node causing repeated work and O(n^2) time
Fix: Combine height and balance check in one recursive function returning both values

Mistake: Checking balance only at root and ignoring subtrees
Fix: Check balance at every node by combining subtree results

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 need to verify tree balance efficiently without repeated height calculations.

The key insight is to return height and balance status together from each subtree in one recursion.

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