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.

Practice

1. What does the diameter of a tree represent in graph theory?

easy

A. The longest path between any two nodes in the tree

B. The number of nodes in the tree

C. The height of the tree from the root

D. The number of leaf nodes in the tree

Solution

1. Step 1: Understand the definition of diameter

   The diameter is the longest path between any two nodes in a tree, not just from the root.

2. Step 2: Differentiate from other tree properties

   Height is the longest path from root to leaf, number of nodes and leaves are counts, not paths.

3. Final Answer:

   The longest path between any two nodes in the tree -> Option A

4. Quick Check:

   Diameter = Longest path [OK]

Hint: Diameter is longest path between any two nodes [OK]

Common Mistakes:

• Confusing diameter with height
• Thinking diameter counts nodes instead of path length
• Assuming diameter is from root only

2. Which TypeScript data structure is best to represent a tree for diameter calculation?

easy

A. Boolean flag

B. String array

C. Number variable

D. Array of edges (adjacency list)

Solution

1. Step 1: Identify tree representation needs

   We need to store connections between nodes, so adjacency list (array of edges) is suitable.

2. Step 2: Eliminate unsuitable types

   String array, number variable, or boolean flag cannot represent node connections effectively.

3. Final Answer:

   Array of edges (adjacency list) -> Option D

4. Quick Check:

   Adjacency list = Array of edges [OK]

Hint: Use adjacency list (array of edges) for tree representation [OK]

Common Mistakes:

• Using simple variables instead of lists
• Confusing data types with tree structure
• Using string arrays for numeric node connections

3. What is the output of the following TypeScript code that calculates the diameter of a tree?

const tree = {
  0: [1, 2],
  1: [0, 3],
  2: [0],
  3: [1]
};

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

let diameter = 0;
dfs(0, -1);
console.log(diameter);

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace DFS from node 0

   From node 0, children are 1 and 2. DFS(1) returns 2 (path 1->3), DFS(2) returns 1. dist from 1: 3, from 2: 2.

2. Step 2: Calculate diameter updates

   At node 0, max1=2, max2=1, diameter updated to 3 (2+1). No larger path found elsewhere.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Longest path length = 3 [OK]

Hint: Sum two longest child paths at each node for diameter [OK]

Common Mistakes:

• Ignoring parent to avoid cycles
• Not updating diameter with sum of two longest paths
• Returning wrong distance from DFS

4. Find the bug in this TypeScript code snippet that tries to compute the diameter of a tree:

const tree = {
  0: [1],
  1: [0, 2],
  2: [1]
};

let diameter = 0;
function dfs(node: number): number {
  let max1 = 0, max2 = 0;
  for (const child of tree[node]) {
    const dist = dfs(child) + 1;
    if (dist > max1) {
      max2 = max1;
      max1 = dist;
    } else if (dist > max2) {
      max2 = dist;
    }
  }
  diameter = Math.max(diameter, max1 + max2);
  return max1;
}
dfs(0);
console.log(diameter);

medium

A. Missing parent parameter to avoid revisiting nodes

B. Diameter variable is not initialized

C. DFS function should return diameter instead of max1

D. Tree is not defined as an array

Solution

1. Step 1: Identify infinite recursion cause

   DFS revisits parent node because no parent check, causing infinite recursion.

2. Step 2: Fix by adding parent parameter

   Pass parent node to DFS and skip it in children loop to avoid cycles.

3. Final Answer:

   Missing parent parameter to avoid revisiting nodes -> Option A

4. Quick Check:

   Parent check prevents infinite recursion [OK]

Hint: Pass parent node in DFS to avoid cycles [OK]

Common Mistakes:

• Not skipping parent node in DFS
• Confusing diameter initialization
• Returning wrong values from DFS

5. Given a weighted tree represented as an adjacency list with edges and weights, how would you modify the diameter calculation to find the longest weighted path?

const tree = {
  0: [{node:1, weight:3}, {node:2, weight:2}],
  1: [{node:0, weight:3}, {node:3, weight:4}],
  2: [{node:0, weight:2}],
  3: [{node:1, weight:4}]
};

hard

A. Ignore weights and count edges only

B. Use BFS instead of DFS without weight consideration

C. Add edge weights to distances during DFS and update diameter accordingly

D. Calculate diameter by counting number of nodes only

Solution

1. Step 1: Incorporate weights in DFS distance calculation

   Instead of adding 1 for each edge, add the edge's weight to the distance.

2. Step 2: Update diameter with sum of two longest weighted paths

   Keep track of two longest weighted distances from children and update diameter with their sum.

3. Final Answer:

   Add edge weights to distances during DFS and update diameter accordingly -> Option C

4. Quick Check:

   Weighted distances sum = diameter [OK]

Hint: Sum edge weights in DFS for weighted diameter [OK]

Common Mistakes:

• Ignoring weights and counting edges only
• Using BFS without weights
• Counting nodes instead of path weights