DP on Trees Diameter of Tree in DSA Typescript - Build from Scratch

DP on Trees: Diameter of Tree

📖 Scenario: Imagine you have a network of connected cities represented as a tree. You want to find the longest path between any two cities in this network. This longest path is called the diameter of the tree.

🎯 Goal: Build a TypeScript program that calculates the diameter of a tree using dynamic programming on trees.

📋 What You'll Learn

Create an adjacency list to represent the tree with exact edges given

Add a variable to keep track of the maximum diameter found

Implement a depth-first search (DFS) function to compute the diameter using DP

Print the final diameter of the tree

💡 Why This Matters

🌍 Real World

Finding the longest path in a network helps in optimizing routes, planning communication lines, or analyzing biological tree structures.

💼 Career

Understanding tree diameters and dynamic programming on trees is useful in software engineering roles involving graph algorithms, network design, and performance optimization.

1

Create the tree as an adjacency list

Create a variable called tree as a Map representing the tree with these exact edges: 0-1, 0-2, 1-3, 1-4, 2-5.

DSA Typescript

// Your code here to create the tree adjacency list

Hint

Use a Map where each key is a node number and the value is an array of connected nodes.

2

Add a variable to track the maximum diameter

Add a variable called maxDiameter and set it to 0 to keep track of the longest path found so far.

DSA Typescript

const tree = new Map();
tree.set(0, [1, 2]);
tree.set(1, [0, 3, 4]);
tree.set(2, [0, 5]);
tree.set(3, [1]);
tree.set(4, [1]);
tree.set(5, [2]);

// Add maxDiameter variable below
// Your code here

Hint

This variable will store the longest path length found during DFS.

3

Implement DFS function to compute diameter

Write a function called dfs that takes node: number and parent: number and returns the longest path length from this node down. Use maxDiameter to update the longest path found by combining the top two longest child paths.

DSA Typescript

const tree = new Map();
tree.set(0, [1, 2]);
tree.set(1, [0, 3, 4]);
tree.set(2, [0, 5]);
tree.set(3, [1]);
tree.set(4, [1]);
tree.set(5, [2]);

let maxDiameter = 0;

// Write dfs function below
// Your code here

Hint

Use DFS to find the two longest paths from children and update maxDiameter with their sum.

4

Call DFS and print the diameter

Call dfs starting from node 0 with parent -1 and then print maxDiameter.

DSA Typescript

const tree = new Map();
tree.set(0, [1, 2]);
tree.set(1, [0, 3, 4]);
tree.set(2, [0, 5]);
tree.set(3, [1]);
tree.set(4, [1]);
tree.set(5, [2]);

let maxDiameter = 0;

function dfs(node: number, parent: number): number {
    let max1 = 0;
    let max2 = 0;
    const neighbors = tree.get(node) || [];
    for (const child of neighbors) {
        if (child === parent) continue;
        const length = dfs(child, node) + 1;
        if (length > max1) {
            max2 = max1;
            max1 = length;
        } else if (length > max2) {
            max2 = length;
        }
    }
    maxDiameter = Math.max(maxDiameter, max1 + max2);
    return max1;
}

// Call dfs and print maxDiameter below
// Your code here

Hint

Start DFS from node 0 with parent -1 and print the maxDiameter after DFS completes.