Check if Binary Tree is Balanced in DSA Javascript - Deep Dive

Overview - Check if Binary Tree is Balanced

What is it?

A binary tree is balanced if for every node, the height difference between its left and right subtrees is at most one. Checking if a binary tree is balanced means verifying this condition for all nodes. This helps ensure the tree is not skewed heavily to one side, which can affect performance. Balanced trees allow faster operations like searching, inserting, and deleting.

Why it matters

Without checking balance, a binary tree can become very uneven, like a tall, skinny tree leaning to one side. This makes operations slow, similar to searching through a long list instead of a well-organized structure. Balanced trees keep operations efficient, which is crucial for fast data access in many applications like databases and file systems.

Where it fits

Before this, learners should understand what binary trees are and how to measure tree height. After this, learners can explore self-balancing trees like AVL or Red-Black trees that maintain balance automatically.

Mental Model

Core Idea

A binary tree is balanced if no node has left and right subtrees differing in height by more than one.

Think of it like...

Imagine a seesaw balanced in the middle; if one side is much heavier (taller), it tips over. A balanced tree is like a seesaw perfectly balanced so it stays level.

       (Root)
       /    \
   (Left)  (Right)
    |        |
 Height L  Height R

Balanced if |Height L - Height R| ≤ 1 for every node

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Height

Concept: Learn how to find the height of a binary tree node recursively.

The height of a node is the number of edges on the longest path from that node down to a leaf. To find height, check the height of left and right children, then take the maximum plus one.

Result

You can calculate the height of any node in the tree.

Knowing how to measure height is essential because balance depends on comparing subtree heights.

2

Foundation

What Makes a Tree Balanced?

Concept: Define the balance condition for every node in the tree.

A node is balanced if the difference between the heights of its left and right subtrees is at most one. The whole tree is balanced if every node meets this condition.

Result

You understand the exact condition that defines a balanced tree.

This condition ensures the tree stays roughly even, preventing long chains on one side.

3

Intermediate

Naive Balance Check with Separate Height Calls

🤔Before reading on: do you think calling height separately for each node is efficient or slow? Commit to your answer.

Concept: Check balance by computing height for each node's subtrees separately, then verify the difference.

For each node, recursively get left and right subtree heights, then check their difference. Recursively do this for all nodes. This works but repeats height calculations many times.

Result

You can check if a tree is balanced but with repeated work causing inefficiency.

Understanding this naive approach reveals why repeated height calculations slow down the check.

4

Intermediate

Optimized Single-Pass Balance Check

🤔Before reading on: can you think of a way to check balance and height in one pass? Commit to your answer.

Concept: Combine height calculation and balance check in one recursive function to avoid repeated work.

Create a function that returns the height if subtree is balanced, or -1 if not. For each node, get left and right heights. If either is -1 or difference > 1, return -1. Otherwise, return max height + 1.

Result

You can check balance efficiently in one traversal of the tree.

This approach saves time by stopping early when imbalance is found and avoiding repeated height calls.

5

Advanced

JavaScript Implementation of Balanced Check

🤔Before reading on: predict the output of checking balance on a tree with root 1, left child 2, and right child 3 with left child 4.

Concept: Implement the optimized balance check in JavaScript with clear comments and test cases.

function isBalanced(root) { function check(node) { if (!node) return 0; const leftHeight = check(node.left); if (leftHeight === -1) return -1; const rightHeight = check(node.right); if (rightHeight === -1) return -1; if (Math.abs(leftHeight - rightHeight) > 1) return -1; return Math.max(leftHeight, rightHeight) + 1; } return check(root) !== -1; } // Example tree: // 1 // / \ // 2 3 // / // 4 const tree = { val: 1, left: { val: 2, left: null, right: null }, right: { val: 3, left: { val: 4, left: null, right: null }, right: null } }; console.log(isBalanced(tree)); // true

Result

true

Seeing the full code and output confirms how the optimized approach works in practice.

6

Expert

Early Termination and Edge Cases

🤔Before reading on: do you think the function stops checking once imbalance is found, or continues fully? Commit to your answer.

Concept: Understand how early termination improves performance and how edge cases like empty trees are handled.

The function returns -1 immediately when imbalance is detected, stopping further checks. This saves time on large trees. Also, empty trees are balanced by definition, returning true. Handling null nodes carefully avoids errors.

Result

The check is efficient and robust for all tree shapes.

Knowing early termination prevents wasted work and handling null nodes avoids bugs in real-world use.

Under the Hood

The balance check uses recursion to explore each node's subtrees. It calculates subtree heights bottom-up, returning -1 if imbalance is found. This propagates up to stop further checks early. The recursion stack holds nodes until their children are processed, ensuring correct height calculation.

Why designed this way?

This design avoids repeated height calculations by combining height and balance checks. Early termination improves performance on large or unbalanced trees. Alternatives like separate height calls were slower and less practical.

Check(node)
  ├─ if node is null: return 0
  ├─ leftHeight = Check(node.left)
  │    └─ if leftHeight == -1: return -1
  ├─ rightHeight = Check(node.right)
  │    └─ if rightHeight == -1: return -1
  ├─ if |leftHeight - rightHeight| > 1: return -1
  └─ return max(leftHeight, rightHeight) + 1

Myth Busters - 4 Common Misconceptions

Quick: Does a balanced tree mean both subtrees have exactly the same height? Commit yes or no.

Common Belief: A balanced tree means the left and right subtrees of every node have exactly the same height.

Reality: Balanced means the height difference is at most one, not exactly equal.

Why it matters: Expecting exact equality can lead to rejecting perfectly balanced trees and misunderstanding the balance condition.

Quick: Is it okay to compute height separately for each node when checking balance? Commit yes or no.

Common Belief: Computing height separately for each node is efficient enough for balance checking.

Reality: This causes repeated calculations, making the check slow (O(n²) time).

Why it matters: Inefficient checks can cause performance issues on large trees, making programs slow or unresponsive.

Quick: Is an empty tree considered balanced? Commit yes or no.

Common Belief: An empty tree is not balanced because it has no nodes.

Reality: An empty tree is balanced by definition since there are no nodes to violate balance.

Why it matters: Misunderstanding this can cause errors or unnecessary checks in code handling empty inputs.

Quick: Does early termination in balance checking risk missing some imbalances? Commit yes or no.

Common Belief: Stopping early when imbalance is found might miss other imbalances deeper in the tree.

Reality: Early termination is safe because one imbalance is enough to declare the whole tree unbalanced.

Why it matters: Knowing this prevents unnecessary full traversal and improves efficiency without losing correctness.

Expert Zone

1

The return value -1 is a sentinel to signal imbalance, cleverly combining height and balance info in one integer.

2

Early termination not only improves speed but also reduces stack usage on large trees, preventing stack overflow.

3

Handling null nodes as height zero simplifies recursion and avoids special cases, a subtle but important design choice.

When NOT to use

This check is for static trees. For dynamic trees with frequent inserts/deletes, use self-balancing trees like AVL or Red-Black trees that maintain balance automatically.

Production Patterns

In production, this check is used for validating tree structures, debugging, or before converting trees to balanced forms. It is often combined with tree traversal utilities and integrated into larger data structure libraries.

Connections

AVL Trees

Builds-on

Understanding balance checking is foundational to AVL trees, which maintain this balance condition after every insertion or deletion.

Divide and Conquer Algorithms

Same pattern

The recursive height and balance check uses divide and conquer by solving subproblems (subtrees) and combining results, a common algorithmic pattern.

Structural Engineering

Analogy in different field

Just like engineers check if a bridge is balanced and stable by measuring forces on parts, balance checking in trees ensures structural stability for efficient operations.

Common Pitfalls

#1 Repeatedly calculating height for each node causes slow performance.

Wrong approach:

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

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

Correct approach:

function check(node) {
if (!node) return 0;
const leftHeight = check(node.left);
if (leftHeight === -1) return -1;
const rightHeight = check(node.right);
if (rightHeight === -1) return -1;
if (Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}

function isBalanced(root) {
return check(root) !== -1;
}

Root cause:

Not combining height and balance checks leads to repeated work and inefficiency.

#2 Assuming empty trees are unbalanced and returning false.

Wrong approach:

function isBalanced(node) {
if (!node) return false; // wrong
// rest of code
}

Correct approach:

function isBalanced(node) {
if (!node) return true; // correct
// rest of code
}

Root cause:

Misunderstanding that an empty tree has no imbalance.

#3 Not stopping recursion early when imbalance is found, wasting time.

Wrong approach:

function check(node) {
if (!node) return 0;
const leftHeight = check(node.left);
const rightHeight = check(node.right);
if (Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}

function isBalanced(root) {
return check(root) !== -1;
}
// But check does not return -1 immediately if leftHeight or rightHeight is -1

Correct approach:

function check(node) {
if (!node) return 0;
const leftHeight = check(node.left);
if (leftHeight === -1) return -1;
const rightHeight = check(node.right);
if (rightHeight === -1) return -1;
if (Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}

function isBalanced(root) {
return check(root) !== -1;
}

Root cause:

Failing to propagate imbalance signal early causes unnecessary recursion.

Key Takeaways

A binary tree is balanced if no node's left and right subtree heights differ by more than one.

Measuring height correctly is essential to checking balance.

Naive balance checks are inefficient due to repeated height calculations.

Combining height and balance checks in one recursive function improves performance and allows early termination.

Understanding balance checking is foundational for advanced balanced trees like AVL and Red-Black trees.

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