DP on Trees Diameter of Tree in DSA Go - 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.Understanding the diameter helps in optimizing communication delays in the network.

🎯 Goal: Build a Go program that uses dynamic programming on trees to find the diameter of a given tree represented by edges.

📋 What You'll Learn

Create a tree using adjacency list representation from given edges

Use a variable to track the maximum diameter found

Implement a DFS function that returns the longest path from a node down to its descendants

Calculate and update the diameter during DFS traversal

Print the diameter of the tree

💡 Why This Matters

🌍 Real World

Finding the diameter of a tree is useful in network design, biology (phylogenetic trees), and organizational hierarchies to understand the longest communication or dependency path.

💼 Career

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

1

Create the tree adjacency list

Create a variable called edges as a slice of integer pairs with these exact values: {{0,1}, {1,2}, {1,3}, {3,4}}. Then create a variable called tree as a map from int to slice of int. Initialize tree as an empty map.

DSA Go

edges := [][]int{{0,1}, {1,2}, {1,3}, {3,4}}
tree := make(map[int][]int)
// Your code here

Hint

Use make(map[int][]int) to create the adjacency list map.

2

Build the adjacency list from edges

Add a for loop with variable edge to iterate over edges. Inside the loop, append the second node to the adjacency list of the first node and vice versa in tree.

DSA Go

package main

import "fmt"

func main() {
    edges := [][]int{{0,1}, {1,2}, {1,3}, {3,4}}
    tree := make(map[int][]int)

    // Build adjacency list from edges
    // Your code here
}

Hint

Remember to add edges in both directions because the tree is undirected.

3

Implement DFS to find diameter

Create a variable diameter of type int and set it to 0. Then define a recursive function dfs that takes node and parent as int and returns an int. Inside dfs, find the top two longest depths from children. Update diameter with the sum of these two depths if it is larger. Return the longest depth plus 1. Call dfs with 0 and -1 in main.

DSA Go

package main

import "fmt"

func main() {
    edges := [][]int{{0,1}, {1,2}, {1,3}, {3,4}}
    tree := make(map[int][]int)

    for _, edge := range edges {
        tree[edge[0]] = append(tree[edge[0]], edge[1])
        tree[edge[1]] = append(tree[edge[1]], edge[0])
    }

    diameter := 0

    var dfs func(node int, parent int) int
    dfs = func(node int, parent int) int {
        // Your code here
    }

    dfs(0, -1)
}

Hint

Track the two longest depths from children to update the diameter.

4

Print the diameter

Write a fmt.Println statement to print the value of diameter.

DSA Go

package main

import "fmt"

func main() {
    edges := [][]int{{0,1}, {1,2}, {1,3}, {3,4}}
    tree := make(map[int][]int)

    for _, edge := range edges {
        tree[edge[0]] = append(tree[edge[0]], edge[1])
        tree[edge[1]] = append(tree[edge[1]], edge[0])
    }

    diameter := 0

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

    dfs(0, -1)

    // Print the diameter
    // Your code here
}

Hint

The diameter is the longest path length between any two nodes. Print the diameter variable.

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