Diameter of Binary Tree in DSA Typescript

Mental Model

The diameter is the longest path between any two nodes in the tree, which may or may not pass through the root.

Analogy: Imagine a tree as a network of roads connecting cities. The diameter is the longest possible trip you can take between two cities without repeating roads.

      1
     / \
    2   3
   / \   \
  4   5   6

Here, arrows show parent to child connections.

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3; 2 -> 4, 5; 3 -> null, 6

Goal: Find the longest path between any two nodes in the tree.

Step 1: Calculate height of node 4 (leaf)

Node 4 height = 0

Why: Leaf nodes have height zero, base for recursion

Step 2: Calculate height of node 5 (leaf)

Node 5 height = 0

Why: Leaf nodes have height zero, base for recursion

Step 3: Calculate height of node 2 using children 4 and 5

Node 2 height = max(0,0) + 1 = 1
Diameter through 2 = 0 + 0 + 2 = 2

Why: Height is max child height + 1; diameter through node is sum of left and right heights plus 2 edges

Step 4: Calculate height of node 6 (leaf)

Node 6 height = 0

Why: Leaf nodes have height zero

Step 5: Calculate height of node 3 using right child 6

Node 3 height = max(-1,0) + 1 = 1
Diameter through 3 = -1 + 0 + 2 = 1

Why: Left child is null (-1 height), right child height 0, so height is 1

Step 6: Calculate height of root node 1 using children 2 and 3

Node 1 height = max(1,1) + 1 = 2
Diameter through 1 = 1 + 1 + 2 = 4

Why: Diameter through root is sum of left and right heights plus 2 edges

Step 7: Compare all diameters found and select maximum

Max diameter = 4

Why: Longest path found is diameter

Result:

Diameter path length = 4 edges (path: 4 -> 2 -> 1 -> 3 -> 6)

Annotated Code

DSA Typescript

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

function diameterOfBinaryTree(root: TreeNode | null): number {
  let maxDiameter = 0;

  function height(node: TreeNode | null): number {
    if (node === null) return -1; // base case: empty subtree

    const leftHeight = height(node.left); // height of left subtree
    const rightHeight = height(node.right); // height of right subtree

    // diameter through current node is leftHeight + rightHeight + 2 edges
    const diameterThroughNode = leftHeight + rightHeight + 2;

    if (diameterThroughNode > maxDiameter) {
      maxDiameter = diameterThroughNode; // update max diameter if larger
    }

    return Math.max(leftHeight, rightHeight) + 1; // height of current node
  }

  height(root);
  return maxDiameter;
}

// Driver code to test
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, null, new TreeNode(6))
);
console.log(diameterOfBinaryTree(root));

if (node === null) return -1; // base case: empty subtree

return -1 for null to count edges correctly

const leftHeight = height(node.left); // height of left subtree

recursively find left subtree height

const rightHeight = height(node.right); // height of right subtree

recursively find right subtree height

const diameterThroughNode = leftHeight + rightHeight + 2;

calculate diameter passing through current node

if (diameterThroughNode > maxDiameter) { maxDiameter = diameterThroughNode; }

update max diameter if current is larger

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

return height of current node for parent's calculation

Output

4

Complexity Analysis

Time: O(n) because we visit each node once to compute heights and diameters

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach recalculates heights repeatedly causing O(n^2) time; this optimized method uses post-order traversal to compute heights once

Edge Cases

Empty tree (root is null)

Returns diameter 0 because no nodes exist

DSA Typescript

if (node === null) return -1;

Single node tree

Diameter is 0 since no edges exist

DSA Typescript

const diameterThroughNode = leftHeight + rightHeight + 2;

Skewed tree (all nodes only on one side)

Diameter equals number of edges in the longest path (height of tree)

DSA Typescript

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

When to Use This Pattern

When asked for the longest path between any two nodes in a tree, use the diameter pattern by combining subtree heights to find max path length.

Common Mistakes

Mistake: Returning node count instead of edge count for diameter
Fix: Return -1 for null nodes so height counts edges, not nodes

Mistake: Recomputing heights multiple times causing slow code
Fix: Use a single post-order traversal to compute heights and update diameter simultaneously

Summary

Finds the longest path between any two nodes in a binary tree measured in edges.

Use when you need the maximum distance between two nodes in a tree structure.

The diameter is the largest sum of left and right subtree heights plus two edges at any node.