DP on Trees Diameter of Tree in DSA Go - Time & Space Complexity

Time Complexity: DP on Trees Diameter of Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the diameter of a tree grows as the tree gets bigger.

Specifically, how does the work change when the number of nodes increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

// Call dfs(0, -1, graph, &diameter) to find diameter

This code finds the diameter of a tree using a depth-first search that calculates the longest paths through each node.

Identify Repeating Operations

Look for loops and recursive calls that repeat work.

• Primary operation: The recursive depth-first search (dfs) visits each node once.
• How many times: Each node is visited exactly one time, and each edge is checked twice (once from each end).

How Execution Grows With Input

As the number of nodes (n) grows, the number of operations grows roughly in the same way.

Input Size (n)	Approx. Operations
10	About 18 (edges checked twice)
100	About 198
1000	About 1998

Pattern observation: The work grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the diameter grows directly in proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "Because the code uses recursion inside a loop, it must be O(n²)."

[OK] Correct: Each node is visited only once, so the total work is proportional to n, not n squared.

Interview Connect

Understanding this linear time approach shows you can handle tree problems efficiently, a key skill in many coding challenges.

Self-Check

"What if we changed the tree to a graph with cycles? How would the time complexity change?"

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