Coding Interview Questions | Balanced Binary Tree

December 20th, 2023

Introduction:

This summary will talk about my solution to the binary search problem as seen on leetcode here.

Solution:

function getHeight(root: TreeNode | null): number {
  if (!root) {
    return 0;
  }

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

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

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);
}

Summary

• In the solution above, the getHeight function recursively calculates the height of a subtree by finding the maximum height between its left and right subtrees, plus 1.
• The isBalanced function checks if the tree is height-balanced by comparing the absolute difference in heights between the left and right subtrees at each node.
• The solution employs recursion in both the height calculation and the check for balance.

Bonus Solution

Here’s a bonus solution that uses a while loop to solve the problem instead of recursion:

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

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

function getHeight(root: TreeNode | null): number {
  if (!root) {
    return 0;
  }

  const stack = [{ node: root, depth: 1 }];
  let maxHeight = 0;

  while (stack.length > 0) {
    const { node, depth } = stack.pop()!;

    if (depth > maxHeight) {
      maxHeight = depth;
    }

    if (node.left) {
      stack.push({ node: node.left, depth: depth + 1 });
    }

    if (node.right) {
      stack.push({ node: node.right, depth: depth + 1 });
    }
  }

  return maxHeight;
}

function isBalanced(root: TreeNode | null): boolean {
  if (!root) {
    return true;
  }

  const stack = [root];

  while (stack.length > 0) {
    const currentNode = stack.pop()!;

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

    if (Math.abs(leftHeight - rightHeight) > 1) {
      return false;
    }

    if (currentNode.left) {
      stack.push(currentNode.left);
    }

    if (currentNode.right) {
      stack.push(currentNode.right);
    }
  }

  return true;
}

This version uses a stack to simulate the recursive traversal and calculates the height of each subtree within the getHeight function using a while loop. The isBalanced function then checks the balance condition using an iterative approach.