DP on Trees Diameter of Tree in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the adjacency list for the tree.

DSA Go

adj := make([][]int, [1])

Drag options to blanks, or click blank then click option'

A0

Bedges

Cn

Ddiameter

Attempts:

3 left

💡 Hint

Common Mistakes

Using the number of edges instead of nodes for adjacency list size.

We create an adjacency list with size equal to the number of nodes n.

2fill in blank

medium

Complete the code to add edges to the adjacency list.

DSA Go

adj[u] = append(adj[u], [1])
adj[v] = append(adj[v], u)

Drag options to blanks, or click blank then click option'

An

Bu

Cdiameter

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Appending u to adj[u] instead of v.

We add node v to the adjacency list of u to represent the edge.

3fill in blank

hard

Fix the error in the DFS function signature to correctly pass the parent node.

DSA Go

func dfs(node int, parent int) int {
    max1, max2 := 0, 0
    for _, child := range adj[node] {
        if child == [1] {
            continue
        }
        dist := dfs(child, node) + 1
        if dist > max1 {
            max2 = max1
            max1 = dist
        } else if dist > max2 {
            max2 = dist
        }
    }
    diameter = max(diameter, max1+max2)
    return max1
}

Drag options to blanks, or click blank then click option'

Adiameter

Bparent

Cnode

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Skipping the wrong node or not skipping any node.

We skip the parent node to avoid revisiting it in DFS.

4fill in blank

hard

Fill both blanks to update the diameter and return the longest path from the current node.

DSA Go

diameter = max(diameter, [1] + [2])
return max1

Drag options to blanks, or click blank then click option'

Amax1

Bmax2

Cdiameter

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using diameter or node instead of max1 and max2.

The diameter is updated by the sum of the two longest paths from the current node.

5fill in blank

hard

Fill all three blanks to complete the main function that computes the diameter of the tree.

DSA Go

func treeDiameter(n int, edges [][]int) int {
    adj := make([][]int, [1])
    for _, e := range edges {
        u, v := e[0], e[1]
        adj[u] = append(adj[u], [2])
        adj[v] = append(adj[v], u)
    }
    diameter := 0
    dfs(0, [3])
    return diameter
}

Drag options to blanks, or click blank then click option'

An

Bv

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong adjacency list size, wrong append node, or wrong DFS parent.

Initialize adjacency list with size n, append v to adj[u], and start DFS from node 0 with parent -1.

Practice

1. What is the diameter of a tree in the context of dynamic programming on trees?

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 tree diameter

   The diameter is the longest path between any two nodes in the tree, not necessarily passing through the root.

2. Step 2: Differentiate from other tree properties

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

3. Final Answer:

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

4. Quick Check:

   Diameter = longest path in tree [OK]

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

Common Mistakes:

• Confusing diameter with height
• Thinking diameter is number of nodes
• Assuming diameter passes through root

2. Which of the following Go code snippets correctly initializes an adjacency list for a tree with n nodes?

easy

A. graph := make([][]int, n)

B. graph := make([]int, n)

C. graph := make(map[int]int)

D. graph := make([]int, 0)

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list for a tree with n nodes is a slice of slices of ints, each inner slice holds neighbors.

2. Step 2: Match Go syntax for adjacency list

   make([][]int, n) creates a slice of n slices of ints, perfect for adjacency list initialization.

3. Final Answer:

   graph := make([][]int, n) -> Option A

4. Quick Check:

   Adjacency list = [][]int slice [OK]

Hint: Adjacency list = slice of slices in Go [OK]

Common Mistakes:

• Using make([]int, n) which is 1D slice
• Using map[int]int which is not adjacency list
• Initializing empty slice without size

3. Given the following Go code to find the diameter of a tree, what is the output?

package main
import "fmt"

var graph [][]int
var maxDiameter int

func dfs(node, parent int) int {
    max1, max2 := 0, 0
    for _, child := range graph[node] {
        if child == parent {
            continue
        }
        length := dfs(child, node) + 1
        if length > max1 {
            max2 = max1
            max1 = length
        } else if length > max2 {
            max2 = length
        }
    }
    if max1+max2 > maxDiameter {
        maxDiameter = max1 + max2
    }
    return max1
}

func main() {
    graph = make([][]int, 5)
    graph[0] = []int{1, 2}
    graph[1] = []int{0, 3}
    graph[2] = []int{0}
    graph[3] = []int{1, 4}
    graph[4] = []int{3}
    dfs(0, -1)
    fmt.Println(maxDiameter)
}

medium

A. 2

B. 4

C. 5

D. 3

Solution

1. Step 1: Understand the tree structure

   The tree edges are: 0-1, 0-2, 1-3, 3-4. The longest path is from node 2 to node 4 via 0,1,3 with length 4 edges.

2. Step 2: Trace DFS and diameter calculation

   DFS calculates max1 and max2 longest paths from children. maxDiameter updates to max1+max2 which is 4 for path 2-0-1-3-4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Longest path length = 4 edges [OK]

Hint: Diameter = longest path edges counted in DFS [OK]

Common Mistakes:

• Counting nodes instead of edges
• Ignoring parent check in DFS
• Misreading tree connections

4. The following Go code attempts to compute the diameter of a tree but produces incorrect results. What is the bug?

func dfs(node, parent int) int {
    max1, max2 := 0, 0
    for _, child := range graph[node] {
        length := dfs(child, node) + 1
        if length > max1 {
            max2 = max1
            max1 = length
        } else if length > max2 {
            max2 = length
        }
    }
    if max1+max2 > maxDiameter {
        maxDiameter = max1 + max2
    }
    return max1
}

medium

A. Wrong update of maxDiameter variable

B. Incorrect initialization of max1 and max2

C. Missing check to skip parent node in DFS

D. Returning max2 instead of max1

Solution

1. Step 1: Analyze DFS loop over children

   The code calls dfs on all children without skipping the parent, causing infinite recursion or wrong paths.

2. Step 2: Identify missing parent check

   To avoid revisiting parent, code must skip child == parent in loop.

3. Final Answer:

   Missing check to skip parent node in DFS -> Option C

4. Quick Check:

   Skip parent in DFS to avoid cycles [OK]

Hint: Always skip parent node in DFS to prevent cycles [OK]

Common Mistakes:

• Forgetting parent skip causes infinite recursion
• Confusing max1 and max2 updates
• Incorrect diameter update logic

5. You want to find the diameter of a weighted tree where edges have positive weights. Which modification to the standard DP on trees diameter algorithm is correct?

hard

A. Use BFS twice without considering weights

B. Ignore edge weights and count edges as 1 each

C. Calculate diameter by summing all edge weights in the tree

D. Replace all increments of 1 with the edge weight when calculating path lengths

Solution

1. Step 1: Understand weighted tree diameter

   Diameter is longest weighted path, so edge weights must be included in path length calculations.

2. Step 2: Modify DP algorithm for weights

   Instead of adding 1 for each edge, add the actual edge weight when updating max1 and max2.

3. Step 3: Reject incorrect options

   Ignoring weights or summing all edges does not find longest path. BFS without weights finds unweighted diameter only.

4. Final Answer:

   Replace all increments of 1 with the edge weight when calculating path lengths -> Option D

5. Quick Check:

   Use edge weights in path sums for weighted diameter [OK]

Hint: Add edge weights instead of 1 for weighted diameter [OK]

Common Mistakes:

• Ignoring weights in diameter calculation
• Summing all edges instead of longest path
• Using unweighted BFS for weighted tree