DP on Trees Diameter of Tree in DSA Go - Execution Trace

Concept Flow - DP on Trees Diameter of Tree

Start at any node

↓

DFS to children

↓

Compute max depths from children

↓

Update diameter with sum of top two depths

↓

Return max depth + 1 to parent

↓

Repeat for all nodes

↓

Diameter is max recorded sum

We start DFS from any node, compute max depths of children, update diameter by sum of top two depths, and propagate max depth up.

Execution Sample

DSA Go

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

This DFS function computes max depths from children, updates diameter, and returns max depth to parent.

Execution Table

Step	Operation	Node Visited	Max Depths from Children	Diameter Update	Return Depth	Visual State
1	Start DFS	0	max1=0, max2=0	diameter=0	-	Tree: 0 connected to 1,2,3
2	Visit child	1	max1=0, max2=0	diameter=0	-	Node 1 leaf
3	Return depth	1	-	-	1	Back to 0
4	Visit child	2	max1=0, max2=0	diameter=0	-	Node 2 leaf
5	Return depth	2	-	-	1	Back to 0
6	Visit child	3	max1=0, max2=0	diameter=0	-	Node 3 has child 4
7	Visit child	4	max1=0, max2=0	diameter=0	-	Node 4 leaf
8	Return depth	4	-	-	1	Back to 3
9	Update max depths	3	max1=1, max2=0	diameter=0	-	Node 3 max depths updated
10	Return depth	3	-	-	2	Back to 0
11	Update max depths	0	max1=2, max2=1	diameter=0	-	Node 0 max depths updated
12	Update diameter	0	-	diameter=3	-	Diameter updated to 3
13	Return depth	0	-	-	3	DFS complete

💡 All nodes visited, diameter is max sum of two max depths found (3)

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 8	After Step 10	After Step 12	Final
diameter	0	0	0	0	0	3	3
max1 (node 0)	0	1	1	1	2	2	2
max2 (node 0)	0	0	1	1	1	1	1
Return depth (node 1)	-	1	-	-	-	-	-
Return depth (node 2)	-	-	1	-	-	-	-
Return depth (node 3)	-	-	-	2	-	-	-
Return depth (node 4)	-	-	-	1	-	-	-

Key Moments - 3 Insights

Why do we update diameter with sum of top two max depths from children?

Because the longest path through the current node uses the two longest child paths combined, as shown in execution_table step 12 where diameter updates to 3.

Why do we return max1 + 1 instead of diameter from dfs?

We return max1 + 1 to represent the max depth from current node to leaf, so parent can use it to compute its max depths, as seen in steps 3,5,8,10,13.

What happens if a node has only one child?

Then max2 remains 0, so diameter update uses max1 + 0, meaning path through that node is just the longest single branch, as in node 3 at step 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 12, what is the diameter value updated to?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Diameter Update' column at step 12 in execution_table.

At which step does the DFS return a depth of 2?

A Step 10

B Step 5

C Step 8

D Step 13

💡 Hint

Look at the 'Return Depth' column in execution_table for value 2.

If node 3 had no child, how would max1 and diameter update at node 0 change?

A max1 would be 2, diameter would be 3

B max1 would be 1, diameter would be 2

C max1 would be 1, diameter would be 3

D max1 would be 0, diameter would be 1

💡 Hint

Refer to variable_tracker for max1 and diameter values and imagine node 3 depth as 0.

Concept Snapshot

DP on Trees Diameter:
- Use DFS from any node
- For each node, find top two max depths from children
- Update diameter = max(diameter, sum of top two depths)
- Return max depth + 1 to parent
- Diameter is max path length between any two nodes

Full Transcript

To find the diameter of a tree using dynamic programming, we run a DFS starting from any node. At each node, we compute the maximum depths from its children. We keep track of the top two maximum depths and update the diameter by summing these two depths if it is larger than the current diameter. We return the maximum depth plus one to the parent node. This process continues until all nodes are visited. The diameter is the maximum sum of two child depths found during traversal. The execution table shows each step visiting nodes, updating max depths, and diameter. The variable tracker records diameter and max depths changes. Key moments clarify why we sum two depths and why we return max depth plus one. The visual quiz tests understanding of diameter updates and depth returns. This method efficiently computes the longest path in a tree.

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