Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Easytree-dfs

Balanced Binary Tree

Problem (restated)

A height-balanced tree has |leftHeight, rightHeight| ≤ 1 at every node. Check if the tree is balanced.

Intuition

Return height from each subtree; if either side is unbalanced or heights differ by >1, bubble a sentinel.

Approaches

Height + flag DFS

Tested only

Time O(n)Space O(h)

Idea. height(node): if either child returns -1 or |hl-hr|>1 return -1; else 1+max.

Walkthrough. Perfect small trees ok; a long chain on one side fails.

Trade-offs. Single DFS O(n) vs naive recompute height O(n²).

Solution

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

export function isBalanced(root: TreeNode | null): boolean {
  const height = (node: TreeNode | null): number => {
    if (!node) return 0;
    const hl = height(node.left);
    if (hl < 0) return -1;
    const hr = height(node.right);
    if (hr < 0) return -1;
    if (Math.abs(hl - hr) > 1) return -1;
    return 1 + Math.max(hl, hr);
  };
  return height(root) >= 0;
}

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

export function isBalanced(root: TreeNode | null): boolean {
  const height = (node: TreeNode | null): number => {
    if (!node) return 0;
    const hl = height(node.left);
    if (hl < 0) return -1;
    const hr = height(node.right);
    if (hr < 0) return -1;
    if (Math.abs(hl - hr) > 1) return -1;
    return 1 + Math.max(hl, hr);
  };
  return height(root) >= 0;
}

Template connection

Tree DFS multi-field return.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?