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

DP on Trees: Diameter of Tree

📖 Scenario: You are working on a network of connected computers represented as a tree. You want to find the longest path between any two computers in this network. This longest path is called the diameter of the tree.Imagine the computers as points connected by cables. The diameter is the longest cable path you can find without looping back.

🎯 Goal: Build a program that calculates the diameter of a tree using dynamic programming on trees. You will represent the tree as an adjacency list, then use a depth-first search to find the diameter.

📋 What You'll Learn

Create an adjacency list to represent the tree with exact edges

Create a variable to track the maximum diameter found

Write a DFS function to compute the longest paths from each node

Print the diameter of the tree after computation

💡 Why This Matters

🌍 Real World

Finding the diameter of a tree is useful in network design, biology (e.g., evolutionary trees), and file system analysis to understand the longest communication or data path.

💼 Career

Understanding tree diameters and dynamic programming on trees is important for software engineers working on graph algorithms, network optimization, and complex data structure problems.

1

Create the tree adjacency list

Create a constant called tree as an object representing the adjacency list of the tree with these exact edges: 1 connected to 2 and 3, 2 connected to 4 and 5, 3 connected to 6.

DSA Javascript

// Your code here

Hint

Use an object where keys are node numbers and values are arrays of connected nodes.

2

Create a variable to track the diameter

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

DSA Javascript

const tree = {
  1: [2, 3],
  2: [1, 4, 5],
  3: [1, 6],
  4: [2],
  5: [2],
  6: [3]
};
// Your code here

Hint

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

3

Write the DFS function to find diameter

Write a function called dfs that takes node and parent as parameters. It should return the longest path length from node downwards. Inside, use an array longestPaths to store the top two longest child paths. Update maxDiameter with the sum of these two paths if it is larger. Return the longest path plus one.

DSA Javascript

const tree = {
  1: [2, 3],
  2: [1, 4, 5],
  3: [1, 6],
  4: [2],
  5: [2],
  6: [3]
};

let maxDiameter = 0;

// Your code here

Hint

Use recursion to explore children, track top two longest paths, and update the diameter.

4

Run DFS and print the diameter

Call dfs starting from node 1 with parent null. Then print the value of maxDiameter.

DSA Javascript

const tree = {
  1: [2, 3],
  2: [1, 4, 5],
  3: [1, 6],
  4: [2],
  5: [2],
  6: [3]
};

let maxDiameter = 0;

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

// Your code here

Hint

Start DFS from node 1 with no parent and print the diameter.

Practice

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

easy

A. The number of leaf nodes in the tree

B. The number of nodes in the tree

C. The height of the tree from the root

D. The longest path between any two 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 D

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 of the following JavaScript code snippets correctly initializes an adjacency list for a tree with 3 nodes?

easy

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

B. const tree = [[1, 2], [], []];

C. const tree = {0: 1, 1: 2, 2: 0};

D. const tree = [0, 1, 2];

Solution

1. Step 1: Understand adjacency list structure

   An adjacency list maps each node to an array of its connected nodes.

2. Step 2: Check each option

   const tree = {0: [1, 2], 1: [0], 2: [0]}; uses an object with arrays for neighbors, correct for adjacency list. const tree = [[1, 2], [], []]; misses reverse edges from 1 and 2 to 0. const tree = {0: 1, 1: 2, 2: 0}; maps nodes to single nodes, not arrays. const tree = [0, 1, 2]; is just a list of nodes, no edges.

3. Final Answer:

   const tree = {0: [1, 2], 1: [0], 2: [0]}; -> Option A

4. Quick Check:

   Adjacency list = Object with arrays [OK]

Hint: Adjacency list maps nodes to arrays of neighbors [OK]

Common Mistakes:

• Using single values instead of arrays for neighbors
• Confusing arrays of nodes with adjacency lists
• Not including reverse edges in undirected tree

3. Consider the following JavaScript code to find the diameter of a tree represented as an adjacency list. What will be the output?

const tree = {0: [1], 1: [0, 2, 3], 2: [1], 3: [1, 4], 4: [3]};
let maxDiameter = 0;
function dfs(node, parent) {
  let max1 = 0, max2 = 0;
  for (const child of tree[node]) {
    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;
}
dfs(0, -1);
console.log(maxDiameter);

medium

A. 3

B. 5

C. 4

D. 2

Solution

1. Step 1: Trace DFS to find longest paths

   Starting at node 0, DFS explores children. The longest path is from node 2 to node 4 passing through 1 and 3, length 3 edges.

2. Step 2: Calculate diameter from max1 + max2

   At node 1, max1=2 (to node 4), max2=1 (to node 2), sum=3 edges. At node 3, max1=1 (to node 4), max2=0, sum=1. The maximum sum found is 3 edges.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Diameter = sum of two longest child paths at any node [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Ignoring the second longest path in calculation
• Not skipping parent node in DFS

4. The following code attempts to compute the diameter of a tree but has a bug. What is the bug?

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

medium

A. Tree adjacency list is incorrectly defined

B. maxDiameter is not updated correctly

C. Missing parent check causes infinite recursion

D. DFS does not return correct path length

Solution

1. Step 1: Identify missing parent check in DFS

   The DFS function does not skip the parent node, causing it to revisit the previous node endlessly, leading to infinite recursion.

2. Step 2: Understand impact of missing parent check

   Without skipping the parent, the DFS calls loop back and forth between nodes, never terminating.

3. Final Answer:

   Missing parent check causes infinite recursion -> Option C

4. Quick Check:

   Always skip parent node in DFS to avoid loops [OK]

Hint: Always pass and skip parent node in DFS [OK]

Common Mistakes:

• Not passing parent node in DFS
• Assuming tree edges are directed
• Updating maxDiameter incorrectly

5. You have a tree with weighted edges represented as an adjacency list: {0: [[1, 3], [2, 5]], 1: [[0, 3], [3, 4]], 2: [[0, 5]], 3: [[1, 4]]}. How would you modify the diameter calculation to find the longest weighted path?

hard

A. Ignore weights and count edges only

B. Add edge weights to the DFS return values and update maxDiameter accordingly

C. Use BFS instead of DFS without weights

D. Sum all weights in the tree and divide by number of edges

Solution

1. Step 1: Incorporate edge weights in DFS

   Modify DFS to add the weight of each edge when calculating path lengths instead of just adding 1.

2. Step 2: Update maxDiameter with weighted sums

   At each node, update maxDiameter with the sum of the two longest weighted paths found among children.

3. Final Answer:

   Add edge weights to the DFS return values and update maxDiameter accordingly -> Option B

4. Quick Check:

   Weighted diameter needs weighted path sums [OK]

Hint: Add weights to path lengths in DFS for weighted diameter [OK]

Common Mistakes:

• Ignoring weights and counting edges only
• Using BFS without weights for diameter
• Summing all weights instead of longest path