Solving Balanced Binary Tree in JavaScript: Step-by-Step Guide

Introduction to Balanced Binary Trees

Balanced binary trees are a fundamental data structure concept that appears frequently in coding interviews and real-world applications. Understanding how to determine whether a binary tree is balanced is essential for any JavaScript developer looking to strengthen their algorithmic problem-solving skills.

What Is a Balanced Binary Tree?

A balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one. In other words, for each node in the tree, the height of its left subtree and the height of its right subtree must differ by at most one. This property must hold true recursively for every node, not just the root.

Formally, a binary tree is considered balanced if:

The left subtree is balanced
The right subtree is balanced
The absolute difference between the heights of the left and right subtrees is at most 1

Why It Matters

Balanced binary trees matter because they guarantee O(log n) time complexity for search, insertion, and deletion operations. When a binary tree becomes unbalanced, it can degenerate into a structure resembling a linked list, where these operations degrade to O(n) time complexity. This performance difference becomes critical when dealing with large datasets.

From an interview perspective, the "Balanced Binary Tree" problem (LeetCode #110) tests your understanding of tree traversal, recursion, and the ability to optimize solutions by avoiding redundant computations. It is one of the most commonly asked tree problems in technical interviews at major tech companies.

Understanding the Problem

Problem Definition

Given a binary tree, determine if it is height-balanced. The tree is represented using TreeNode objects, where each node has a val, a left child, and a right child.

Here is the standard TreeNode definition used in most coding platforms:

function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val);
  this.left = (left === undefined ? null : left);
  this.right = (right === undefined ? null : right);
}

Examples to Clarify

Consider the following balanced tree:

This tree is balanced because:

Node 3: left subtree height = 1, right subtree height = 2, difference = 1 (balanced)
Node 20: left subtree height = 1, right subtree height = 1, difference = 0 (balanced)
All leaf nodes are trivially balanced

Now consider this unbalanced tree:

This tree is unbalanced because at node 1, the left subtree has a height of 3 while the right subtree has a height of 1, giving a difference of 2, which exceeds the allowed maximum of 1.

Approaches to Solve the Problem

Naive Approach: Top-Down Recursion

The most intuitive approach is to check the balance condition at every node by computing the heights of its left and right subtrees. For each node, you calculate the height of both subtrees, check if their difference is at most 1, and then recursively verify that both subtrees are also balanced.

While this approach is straightforward, it has a significant drawback: it computes the height of the same subtrees multiple times. The time complexity becomes O(n²) in the worst case (when the tree is skewed), because for each of the n nodes, you may traverse up to O(n) nodes to compute the height.

Optimized Approach: Bottom-Up Recursion

The optimized approach uses a bottom-up strategy where you compute the height and check balance in a single pass. Instead of computing heights separately from the balance check, you return the height from each recursive call and simultaneously detect imbalances.

The key insight is that if any subtree is unbalanced, you can short-circuit and propagate that information upward without continuing unnecessary computations. This reduces the time complexity to O(n) since each node is visited exactly once.

Step-by-Step Implementation

Step 1: The Height Helper Function

First, let us create a helper function that computes the height of a tree. This function will be used in the naive approach:

function getHeight(node) {
  if (node === null) {
    return 0;
  }
  const leftHeight = getHeight(node.left);
  const rightHeight = getHeight(node.right);
  return Math.max(leftHeight, rightHeight) + 1;
}

This function recursively computes the height by taking the maximum of the left and right subtree heights and adding 1 for the current node. A null node has a height of 0.

Step 2: Naive Solution Implementation

Using the height helper, we can implement the naive top-down solution:

function isBalanced(root) {
  if (root === null) {
    return true;
  }

  const leftHeight = getHeight(root.left);
  const rightHeight = getHeight(root.right);

  const heightDiff = Math.abs(leftHeight - rightHeight);

  if (heightDiff > 1) {
    return false;
  }

  return isBalanced(root.left) && isBalanced(root.right);
}

This solution works correctly but is inefficient. For each node, it calls getHeight on both subtrees, and then recursively calls isBalanced on both subtrees, which again calls getHeight. This leads to redundant height calculations.

Step 3: Optimized Solution Implementation

Now let us implement the optimized bottom-up approach. The idea is to return a special value (such as -1) when a subtree is found to be unbalanced, allowing us to short-circuit immediately:

function isBalanced(root) {
  function checkHeight(node) {
    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;
  }

  return checkHeight(root) !== -1;
}

Let us break down how this works:

The inner function checkHeight returns the height of the subtree if it is balanced, or -1 if it is unbalanced
After computing the left subtree height, we immediately check if it returned -1 and propagate that upward
Similarly, after computing the right subtree height, we check for -1
If both subtrees are balanced, we check whether the current node maintains the balance property
If the height difference exceeds 1, we return -1 to signal imbalance
Otherwise, we return the actual height of the current subtree

Step 4: Alternative Using a Result Object

Some developers prefer a more explicit approach using an object to carry both the height and balance status. This avoids the magic number -1 and can make the code more readable:

function isBalanced(root) {
  function check(node) {
    if (node === null) {
      return { balanced: true, height: 0 };
    }

    const left = check(node.left);
    if (!left.balanced) {
      return { balanced: false, height: 0 };
    }

    const right = check(node.right);
    if (!right.balanced) {
      return { balanced: false, height: 0 };
    }

    const heightDiff = Math.abs(left.height - right.height);
    const balanced = heightDiff <= 1;
    const height = Math.max(left.height, right.height) + 1;

    return { balanced, height };
  }

  return check(root).balanced;
}

This approach is functionally identical but communicates intent more clearly. The trade-off is slightly more memory usage due to object creation at each node.

Testing the Solution

Building Test Trees

To verify our solution, let us create test cases covering balanced trees, unbalanced trees, edge cases, and more:

// Helper to build a tree from an array (level-order)
function buildTree(arr) {
  if (arr.length === 0 || arr[0] === null) {
    return null;
  }
  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;
  while (queue.length > 0 && i < arr.length) {
    const node = queue.shift();
    if (i < arr.length && arr[i] !== null) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }
    i++;
    if (i < arr.length && arr[i] !== null) {
      node.right = new TreeNode(arr[i]);
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

// Test Case 1: Balanced tree
const tree1 = buildTree([3, 9, 20, null, null, 15, 7]);
console.log(isBalanced(tree1)); // Expected: true

// Test Case 2: Unbalanced tree
const tree2 = buildTree([1, 2, 2, 3, 3, null, null, 4, 4]);
console.log(isBalanced(tree2)); // Expected: false

// Test Case 3: Empty tree
const tree3 = buildTree([]);
console.log(isBalanced(tree3)); // Expected: true

// Test Case 4: Single node
const tree4 = buildTree([1]);
console.log(isBalanced(tree4)); // Expected: true

// Test Case 5: Left-skewed tree (unbalanced)
const tree5 = buildTree([1, 2, null, 3, null, 4, null]);
console.log(isBalanced(tree5)); // Expected: false

// Test Case 6: Right-skewed tree (unbalanced)
const tree6 = buildTree([1, null, 2, null, 3, null, 4]);
console.log(isBalanced(tree6)); // Expected: false

Running these test cases should confirm that the solution handles all scenarios correctly. The empty tree and single-node tree are important edge cases that should not be overlooked.

Complexity Analysis

Time Complexity

The optimized solution has a time complexity of O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once during the bottom-up traversal. The short-circuit mechanism ensures that once an imbalance is detected, no further unnecessary computations are performed.

Space Complexity

The space complexity is O(h), where h is the height of the tree. This accounts for the recursion stack. In the best case (a balanced tree), h = O(log n). In the worst case (a skewed tree), h = O(n). For the naive approach, the space complexity remains O(h) for the recursion stack, but the time complexity degrades to O(n²).

Best Practices

Choose the Right Approach

Always prefer the bottom-up optimized approach over the naive top-down approach. The optimized version is not only more efficient but also demonstrates a deeper understanding of tree traversal patterns. In an interview setting, mentioning both approaches and explaining the trade-offs shows analytical thinking.

Handle Edge Cases Explicitly

Make sure your solution handles edge cases such as an empty tree (null root), a single-node tree, and completely skewed trees. These cases are common in test suites and can reveal subtle bugs in your implementation.

Use Clear Variable Names

Avoid cryptic variable names. Use descriptive names like leftHeight, rightHeight, and heightDiff instead of single letters. This makes your code easier to read and maintain, especially when revisiting it after some time.

Consider Iterative Solutions

While recursive solutions are elegant, extremely deep trees can cause stack overflow errors in JavaScript. For production environments dealing with very large trees, consider an iterative post-order traversal using an explicit stack. Here is a sketch of how that might look:

function isBalanced(root) {
  if (root === null) return true;

  const stack = [];
  const heights = new Map();
  let node = root;
  let lastVisited = null;

  while (stack.length > 0 || node !== null) {
    if (node !== null) {
      stack.push(node);
      node = node.left;
    } else {
      const peekNode = stack[stack.length - 1];
      if (peekNode.right !== null && lastVisited !== peekNode.right) {
        node = peekNode.right;
      } else {
        const current = stack.pop();
        const leftH = heights.get(current.left) || 0;
        const rightH = heights.get(current.right) || 0;

        if (Math.abs(leftH - rightH) > 1) {
          return false;
        }

        heights.set(current, Math.max(leftH, rightH) + 1);
        lastVisited = current;
      }
    }
  }

  return true;
}

This iterative approach uses a post-order traversal pattern and stores computed heights in a Map. It avoids recursion entirely, making it safe for very deep trees.

Test Thoroughly

Always test your solution with a variety of inputs. Beyond the basic test cases, consider trees where only one subtree is deep, trees where the imbalance occurs deep in the structure rather than at the root, and trees with negative values or duplicate values to ensure your logic is robust.

Common Pitfalls to Avoid

Forgetting to check all nodes: Some developers only check the balance at the root node, forgetting that every subtree must also be balanced. Always verify the balance condition recursively for all nodes.
Incorrect height calculation: Remember that the height of a null node is 0, not -1. Mixing up these conventions can lead to off-by-one errors in your balance checks.
Not short-circuiting: In the optimized approach, failing to check for the -1 sentinel value immediately after each recursive call defeats the purpose of the optimization and can lead to unnecessary computations.
Confusing depth and height: Depth is the distance from the root to a node, while height is the distance from a node to its deepest descendant. The balance condition uses height, not depth.

Conclusion

Solving the Balanced Binary Tree problem in JavaScript is an excellent exercise in understanding tree traversal, recursion, and algorithm optimization. The naive top-down approach provides a clear conceptual foundation, while the optimized bottom-up approach demonstrates how to eliminate redundant computations by combining height calculation with balance checking in a single pass. By mastering both approaches, understanding their time and space complexities, and being aware of common pitfalls, you will be well-equipped to tackle this problem and similar tree-based challenges in coding interviews and real-world development scenarios. Remember to always test your solution against edge cases, use clear and descriptive variable names, and consider iterative alternatives when dealing with potentially deep tree structures in production environments.