DP on Trees Diameter of Tree in DSA Javascript

Mental Model

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

Analogy: Imagine a network of roads connecting towns. The diameter is the longest route you can travel without repeating roads. We find it by looking at the longest roads from each town and combining them.

    1
   / \
  2   3
 /     \
4       5

Each number is a town (node), lines are roads (edges).

Dry Run Walkthrough

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

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

Step 1: Start DFS from node 1 to calculate longest paths down each subtree

At node 1: children are 2 and 3

Why: We need to find longest paths from each node to its descendants

Step 2: At node 2, explore child 4; node 4 has no children, so longest path down is 1

Node 4: longest path down = 1

Why: Leaf nodes have longest path down 1

Step 3: Calculate node 2's longest path down as 1 + max of children's longest paths (1 + 1 = 2)

Node 2: longest path down = 2 (2-4)

Why: Longest path down = 1 + max child's longest path down

Step 4: At node 3, explore child 5; node 5 has no children, longest path down = 1

Node 5: longest path down = 1

Why: Leaf nodes have longest path down 1

Step 5: Calculate node 3's longest path down as 1 + max of children's longest paths (1 + 1 = 2)

Node 3: longest path down = 2 (3-5)

Why: Longest path down = 1 + max child's longest path down

Step 6: At node 1, longest paths down children are 2 (node 2) and 2 (node 3). Diameter through node 1 is sum: 2 + 2 = 4

Diameter candidate at node 1 = 4

Why: Longest path through node is sum of two longest child paths

Step 7: Compare diameter candidates from all nodes; max is 4 edges (path 4-2-1-3-5)

Diameter = 4 edges (4 to 5 through 2,1,3)

Why: Diameter is longest path between any two nodes

Result:

Diameter path: 4 -> 2 -> 1 -> 3 -> 5
Diameter length: 4 edges

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val) {
    this.val = val;
    this.children = [];
  }
}

function treeDiameter(root) {
  let diameter = 0;

  function dfs(node) {
    if (!node) return 0;
    let max1 = 0, max2 = 0;
    for (const child of node.children) {
      const length = dfs(child);
      if (length > max1) {
        max2 = max1;
        max1 = length;
      } else if (length > max2) {
        max2 = length;
      }
    }
    diameter = Math.max(diameter, max1 + max2);
    return max1 + 1;
  }

  dfs(root);
  return diameter;
}

// Build tree from example
const node1 = new TreeNode(1);
const node2 = new TreeNode(2);
const node3 = new TreeNode(3);
const node4 = new TreeNode(4);
const node5 = new TreeNode(5);

node1.children.push(node2, node3);
node2.children.push(node4);
node3.children.push(node5);

console.log("Diameter length:", treeDiameter(node1));

let diameter = 0;

Initialize diameter to track longest path found

function dfs(node) {

Start DFS to compute longest paths down from each node

if (!node) return 0;

Base case: no node means path length 0

for (const child of node.children) {

Traverse all children to find their longest paths

const length = dfs(child);

Recursively get longest path down from child

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

Keep track of top two longest child paths

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

Update diameter if sum of two longest child paths is bigger

return max1 + 1;

Return longest path down from current node including edge to child

Output

Diameter length: 4

Complexity Analysis

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

Space: O(n) due to recursion stack in worst case of skewed tree

vs Alternative: Naive approach checking all pairs of nodes is O(n^2), this DP method is much faster

Edge Cases

Single node tree

Diameter is 0 because no edges exist

DSA Javascript

if (!node) return 0;

Linear tree (chain)

Diameter equals number of edges in chain

DSA Javascript

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

Tree with multiple branches of same length

Diameter correctly picks sum of two longest child paths

DSA Javascript

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

When to Use This Pattern

When asked for longest path between any two nodes in a tree, use DP on trees to find longest paths down children and combine them for diameter.

Common Mistakes

Mistake: Returning max1 instead of max1 + 1 in DFS, missing edge count
Fix: Return max1 + 1 to include edge from current node to child

Mistake: Updating diameter with only max1 instead of sum of max1 and max2
Fix: Update diameter with max1 + max2 to consider paths through current node

Summary

Finds the longest path between any two nodes in a tree using 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.

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