DP on Trees Diameter of Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Diameter Calculation on a Simple Tree

What is the output of the following Go code that calculates the diameter of a tree represented as an adjacency list?

DSA Go

package main

import "fmt"

var (
    graph = [][]int{{1, 2}, {0, 3, 4}, {0}, {1}, {1}}
    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() {
    dfs(0, -1)
    fmt.Println(maxDiameter)
}

A 5

B 4

C 2

D 3

💡 Hint

Think about the longest path between any two nodes in the tree.

The diameter is the longest path between two nodes. The longest path here is from node 2 to node 3 or 4 through node 0 and 1, which has length 3 edges.

🧠 Conceptual

intermediate

Understanding Diameter Calculation Logic

In the diameter calculation using DP on trees, why do we keep track of the two longest paths from a node's children?

A To count the total number of nodes in the subtree

B To calculate the height of the tree from that node

C To find the longest path passing through that node by combining two longest child paths

D To find the shortest path between two nodes

💡 Hint

Diameter can pass through a node connecting two longest child paths.

The diameter may pass through a node connecting two longest paths from its children, so tracking the top two longest paths helps find the maximum diameter.

🔧 Debug

advanced

Identify the Bug in Diameter Calculation Code

What error will the following Go code produce when calculating the diameter of a tree?

DSA Go

package main

import "fmt"

var (
    graph = [][]int{{1}, {0, 2}, {1}}
    maxDiameter int
)

func dfs(node int, 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() {
    dfs(0, -1)
    fmt.Println(maxDiameter)
}

A Stack overflow due to infinite recursion

B Prints 2 correctly

C Prints 0 because maxDiameter is never updated

D Compilation error due to missing return

💡 Hint

Check the base case or the condition to skip the parent node.

The condition 'if child == node' is wrong; it should be 'if child == parent' to avoid revisiting the parent and causing infinite recursion.

❓ Predict Output

advanced

Diameter Output for a Star-Shaped Tree

What is the output of the diameter calculation for the following star-shaped tree?

DSA Go

package main

import "fmt"

var (
    graph = [][]int{{1, 2, 3, 4}, {0}, {0}, {0}, {0}}
    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() {
    dfs(0, -1)
    fmt.Println(maxDiameter)
}

A 3

B 2

C 1

D 4

💡 Hint

The diameter is the longest path between two leaf nodes through the center.

In a star-shaped tree, the longest path is between any two leaves through the center node, which has length 2 edges.

🚀 Application

expert

Maximum Diameter After Adding One Edge

Given a tree with 5 nodes and edges [[0,1],[1,2],[1,3],[3,4]], what is the maximum possible diameter after adding exactly one new edge between any two nodes?

A 4

B 3

C 5

D 6

💡 Hint

Adding an edge can create a cycle and potentially increase the longest path.

Original diameter is 3 (path 2-1-3-4). Adding an edge between nodes 2 and 4 creates a cycle and a longer path of length 4.

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