DP on Trees Diameter of Tree in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the diameter of a tree?

The diameter of a tree is the longest path between any two nodes in the tree. It can pass through or not pass through the root.

intermediate

How can dynamic programming help find the diameter of a tree?

Dynamic programming stores the longest path from each node to its descendants, allowing efficient calculation of the diameter by combining these paths.

beginner

In the diameter calculation, what does the 'height' of a node represent?

The height of a node is the length of the longest path from that node down to a leaf node in its subtree.

intermediate

Why do we consider the sum of the two largest heights of children nodes when computing the diameter at a node?

Because the longest path through that node can be formed by joining the two longest paths from its children, passing through the node itself (sum of the two largest child heights + 2).

intermediate

What is the time complexity of finding the diameter of a tree using DP?

The time complexity is O(n), where n is the number of nodes, because each node is visited once during the DFS traversal.

What does the diameter of a tree represent?

A Longest path between any two nodes

B Number of nodes in the tree

C Height of the root node

D Number of leaf nodes

The diameter is the longest path between any two nodes in the tree.

Which technique helps efficiently find the diameter of a tree?

A Greedy Algorithm

B Sorting

C Binary Search

D Dynamic Programming

Dynamic Programming stores intermediate results to avoid repeated calculations.

When calculating diameter at a node, which two values are summed?

A Height and depth of the node

B Two smallest heights of its children

C Two largest heights of its children

D Number of children

The diameter through a node is the sum of the two largest heights from its children plus 2.

What is the height of a leaf node?

A Depends on the tree

B 0

C 1

D Infinity

A leaf node has height 0 because it has no children.

What is the time complexity of the DP approach to find tree diameter?

A O(n)

B O(n^2)

C O(log n)

D O(1)

Each node is visited once, so the complexity is linear in the number of nodes.

Explain how dynamic programming is used to find the diameter of a tree.

Think about how you can reuse results from child nodes to find the longest path.

Describe the steps to calculate the diameter of a tree using a depth-first search.

Focus on what you do at each node during the DFS.

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