Depth, Height, and Diameter

Many tree problems reduce to a single question: “what is the best (or worst) property of my subtree?” The answer at each node depends on the answers from its children. That parent-after-children dependency is postorder traversal, and computing a value from children up to the parent is bottom-up dynamic programming on the tree.

Max Depth (Height)

The height of a node is 1 plus the height of its taller child. A null node has height -1 (or 0 if you define height as number of nodes rather than edges).

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

// Returns number of edges on the longest root-to-leaf path.
function maxDepth(node) {
  if (!node) return -1;
  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

// Equivalently, number of nodes on the longest path:
function maxDepthNodes(node) {
  if (!node) return 0;
  return 1 + Math.max(maxDepthNodes(node.left), maxDepthNodes(node.right));
}

LeetCode’s “Maximum Depth of Binary Tree” uses the node-count convention (maxDepthNodes), returning 0 for null and 1 for a single-node tree.

Min Depth

Min depth is subtler: it is the path length to the nearest leaf, not the nearest null. A node with only one child must not treat the null side as a leaf path.

function minDepth(node) {
  if (!node) return 0;
  if (!node.left && !node.right) return 1;   // leaf
  if (!node.left)  return 1 + minDepth(node.right);
  if (!node.right) return 1 + minDepth(node.left);
  return 1 + Math.min(minDepth(node.left), minDepth(node.right));
}

Diameter

The diameter is the length of the longest path between any two nodes in the tree. That path may or may not pass through the root. At each node, the longest path passing through it is leftHeight + rightHeight. Track the global maximum during a single postorder DFS.

function diameterOfBinaryTree(root) {
  let maxDiameter = 0;

  function height(node) {
    if (!node) return -1;
    const left  = height(node.left);
    const right = height(node.right);
    // path through this node spans left + right + 2 edges
    maxDiameter = Math.max(maxDiameter, left + right + 2);
    return 1 + Math.max(left, right);
  }

  height(root);
  return maxDiameter;
}

// Example:
//       1
//      / \
//     2   3
//    / \
//   4   5
// diameter = 3  (path: 4 -> 2 -> 1 -> 3  or  5 -> 2 -> 1 -> 3)

Using a closure for maxDiameter lets us return height (needed by the parent) while updating the global diameter as a side effect — a common pattern for tree problems that need two values from one DFS.

Why One Pass Is Enough

A naive approach would compute the height of every node separately (O(n) per node, O(n²) total). The bottom-up pass computes height once per node and propagates it upward, giving O(n) overall.

h is O(log n) for balanced trees, O(n) worst case for degenerate ones.

Up Next

With height mastered, we can tackle the lowest common ancestor — a classic interview problem that uses the same bottom-up reasoning.