DP on Trees Diameter of Tree in DSA Typescript

Mental Model

The diameter of a tree is the longest path between any two nodes. We find it by exploring the longest paths from each node using dynamic programming.

Analogy: Imagine a network of roads connecting cities (nodes). The diameter is the longest route you can drive without repeating roads. To find it, you check the longest routes starting from each city and combine them.

    1
   / \
  2   3
 /     \
4       5

Nodes connected like a tree with branches.

Dry Run Walkthrough

Input: Tree edges: 1-2, 1-3, 2-4, 3-5

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

Step 1: Start DFS from node 1, calculate longest path down each subtree

At node 4: longest path down is 0 (leaf)
At node 5: longest path down is 0 (leaf)

Why: Leaf nodes have no children, so longest downward path is 0

Step 2: At node 2, longest downward path is max of child (node 4) + 1 = 1

Node 2 longest downward path = 1
Node 4 longest downward path = 0

Why: Add 1 for edge from node 2 to node 4

Step 3: At node 3, longest downward path is max of child (node 5) + 1 = 1

Node 3 longest downward path = 1
Node 5 longest downward path = 0

Why: Add 1 for edge from node 3 to node 5

Step 4: At node 1, longest downward paths from children are 1 (node 2) and 1 (node 3)

Node 1 children longest downward paths = [1, 1]

Why: We need these to compute diameter passing through node 1

Step 5: Calculate diameter at node 1 as sum of top two longest downward paths = 1 + 1 = 2

Diameter candidate at node 1 = 2

Why: Longest path passes through node 1 connecting node 4 and node 5

Step 6: Compare diameter candidates from all nodes, max is 2

Final diameter = 2

Why: Diameter is the longest path found in the tree

Result:

2

Annotated Code

DSA Typescript

class Tree {
  adjacencyList: Map<number, number[]> = new Map();

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  diameter(): number {
    let diameter = 0;
    const visited = new Set<number>();

    const dfs = (node: number): number => {
      visited.add(node);
      let max1 = 0, max2 = 0;

      for (const neighbor of this.adjacencyList.get(node) || []) {
        if (!visited.has(neighbor)) {
          const length = dfs(neighbor) + 1;
          if (length > max1) {
            max2 = max1;
            max1 = length;
          } else if (length > max2) {
            max2 = length;
          }
        }
      }

      diameter = Math.max(diameter, max1 + max2);
      return max1;
    };

    dfs(1);
    return diameter;
  }
}

// Driver code
const tree = new Tree();
tree.addEdge(1, 2);
tree.addEdge(1, 3);
tree.addEdge(2, 4);
tree.addEdge(3, 5);
console.log(tree.diameter());

const dfs = (node: number): number => {

start DFS to explore longest downward paths from node

visited.add(node);

mark node as visited to avoid cycles

for (const neighbor of this.adjacencyList.get(node) || []) {

iterate over neighbors to explore subtrees

if (!visited.has(neighbor)) {

only visit unvisited neighbors to prevent revisiting

const length = dfs(neighbor) + 1;

compute longest path length from neighbor plus edge

if (length > max1) { max2 = max1; max1 = length; } else if (length > max2) { max2 = length; }

track top two longest downward paths from children

diameter = Math.max(diameter, max1 + max2);

update diameter with sum of two longest paths through current node

return max1;

return longest downward path for parent's calculation

Output

2

Complexity Analysis

Time: O(n) because we visit each node once during DFS

Space: O(n) for recursion stack and adjacency list storage

vs Alternative: Naive approach checking all pairs is O(n^2), DP on trees reduces it to O(n)

Edge Cases

Single node tree

Diameter is 0 because no edges exist

DSA Typescript

visited.add(node);

Linear tree (chain)

Diameter equals number of edges in chain

DSA Typescript

diameter = Math.max(diameter, max1 + max2);

Tree with multiple branches of same length

Diameter correctly picks longest path through two longest branches

DSA Typescript

if (length > max1) { max2 = max1; max1 = length; } else if (length > max2) { max2 = length; }

When to Use This Pattern

When asked to find longest path in a tree, use DP on trees by DFS to find longest downward paths and combine them for diameter.

Common Mistakes

Mistake: Not tracking two longest paths from children, only one
Fix: Track top two longest downward paths to compute diameter passing through node

Summary

Finds the longest path between any two nodes in a tree using DFS and dynamic programming.

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

The diameter is the sum of the two longest downward paths from a node.