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

Concept Flow - DP on Trees Diameter of Tree

Start at any node

↓

Run DFS to find farthest node A

↓

Run DFS from node A to find farthest node B

↓

Diameter = distance between A and B

↓

Use DP to store max depths at each node

↓

Calculate max diameter using depths

↓

Return diameter

Find the tree diameter by two DFS traversals and use DP to store max depths for efficient calculation.

Execution Sample

DSA Python

def dfs(node, parent):
    max1 = max2 = 0
    for child in graph[node]:
        if child == parent:
            continue
        depth = dfs(child, node) + 1
        if depth > max1:
            max2 = max1
            max1 = depth
        elif depth > max2:
            max2 = depth
    diameter[0] = max(diameter[0], max1 + max2)
    return max1

DFS calculates max depths of subtrees and updates diameter by sum of top two depths.

Execution Table

Step	Operation	Current Node	Max Depths (max1, max2)	Diameter Update	Visual State (Tree with depths)
1	Start DFS at node 1	1	(0, 0)	0	1(0)
2	Visit child node 2	2	(0, 0)	0	1(0) - 2(0)
3	Visit child node 4	4	(0, 0)	0	1(0) - 2(0) - 4(0)
4	Return from node 4 to 2	2	(1, 0)	0	1(0) - 2(1) - 4(0)
5	Visit child node 5	5	(0, 0)	0	1(0) - 2(1) - 5(0)
6	Return from node 5 to 2	2	(1, 1)	2	1(0) - 2(1) - 5(0)
7	Return from node 2 to 1	1	(2, 0)	2	1(2) - 2(1) - 5(0)
8	Visit child node 3	3	(0, 0)	2	1(2) - 3(0)
9	Visit child node 6	6	(0, 0)	2	1(2) - 3(0) - 6(0)
10	Return from node 6 to 3	3	(1, 0)	2	1(2) - 3(1) - 6(0)
11	Visit child node 7	7	(0, 0)	2	1(2) - 3(1) - 7(0)
12	Return from node 7 to 3	3	(1, 1)	3	1(2) - 3(1) - 7(0)
13	Return from node 3 to 1	1	(2, 2)	4	1(2) - 3(2) - 7(0)
14	DFS complete, diameter found	-	-	4	Diameter = 4

💡 DFS completes after visiting all nodes; diameter is max sum of two max depths at any node.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 10	After Step 12	After Step 13	Final
diameter[0]	0	0	2	2	2	3	4	4
max1 (at node 2)	0	1	1	1	-	-	-	-
max2 (at node 2)	0	0	1	1	-	-	-	-
max1 (at node 3)	0	-	-	-	1	1	2	-
max2 (at node 3)	0	-	-	-	0	1	2	-
max1 (at node 1)	0	-	-	2	-	-	2	2
max2 (at node 1)	0	-	-	0	-	-	2	2

Key Moments - 3 Insights

Why do we keep track of two max depths (max1 and max2) at each node?

Because the diameter can pass through the current node by combining the two longest paths from its children. This is shown in execution_table rows 6 and 13 where diameter updates use max1 + max2.

Why do we add 1 to the depth returned by child nodes in DFS?

Adding 1 accounts for the edge between the current node and the child node, as seen in execution_table rows 4 and 10 where depth is returned as child's depth + 1.

Why does the diameter update happen inside the DFS function?

Because at each node, we can calculate the longest path passing through it using max1 + max2. Updating diameter during DFS ensures we consider all nodes, as shown in execution_table rows 6, 12, and 13.

Visual Quiz - 3 Questions

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

A 1

B 0

C 2

D 3

💡 Hint

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

At which step does the diameter first update to 3?

A Step 12

B Step 13

C Step 10

D Step 7

💡 Hint

Look at the 'Diameter Update' column and find when it changes to 3.

If we remove node 7 from the tree, how would the final diameter change?

A Diameter remains 4

B Diameter decreases to 3

C Diameter increases

D Diameter becomes 2

💡 Hint

Removing node 7 reduces max2 at node 3, check variable_tracker for max depths at node 3.

Concept Snapshot

DP on Trees Diameter:
- Use DFS to find max depths of subtrees
- Track two largest depths (max1, max2) at each node
- Diameter = max sum of max1 + max2 over all nodes
- Update diameter during DFS
- Return diameter after full traversal

Full Transcript

To find the diameter of a tree using DP, we run a DFS from any node. At each node, we calculate the two longest depths from its children, called max1 and max2. The diameter can be the sum of these two depths if the longest path passes through this node. We update the diameter during DFS by comparing the current diameter with max1 + max2. After visiting all nodes, the diameter variable holds the longest path length in the tree. This method efficiently computes diameter in one DFS traversal by storing subtree depths.

Practice

1. What is the diameter of a tree in terms of its nodes?

easy

A. The total number of nodes in the tree

B. The number of leaf nodes in the tree

C. The longest path between any two nodes in the tree

D. The height of the tree from the root node

Solution

1. Step 1: Understand the definition of tree diameter

   The diameter is the longest path between any two nodes, not just from the root or leaf count.

2. Step 2: Compare options with definition

   Only The longest path between any two nodes in the tree correctly describes the longest path between any two nodes.

3. Final Answer:

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

4. Quick Check:

   Diameter = longest path [OK]

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

Common Mistakes:

• Confusing diameter with tree height
• Thinking diameter is number of leaves
• Assuming diameter is total nodes count

2. Which of the following is the correct Python syntax to declare a recursive function to find the diameter of a tree?

easy

A. def diameter(node):

B. function diameter(node) {

C. def diameter[node]:

D. diameter = lambda node:

Solution

1. Step 1: Identify correct Python function syntax

   Python functions use 'def' keyword followed by function name and parentheses with parameters.

2. Step 2: Check each option

   def diameter(node): uses correct Python syntax. function diameter(node) { is JavaScript style. def diameter[node]: uses wrong brackets. diameter = lambda node: is incomplete lambda syntax.

3. Final Answer:

   def diameter(node): -> Option A

4. Quick Check:

   Python function syntax = def name(params): [OK]

Hint: Python functions start with def and parentheses [OK]

Common Mistakes:

• Using curly braces instead of colon
• Using square brackets for parameters
• Incorrect lambda syntax for recursion

3. Given the following tree edges and code snippet, what is the diameter of the tree?

edges = [(1,2), (2,3), (2,4), (4,5)]

# Code snippet
from collections import defaultdict

tree = defaultdict(list)
for u,v in edges:
    tree[u].append(v)
    tree[v].append(u)

max_diameter = 0
def dfs(node, parent):
    global max_diameter
    max1 = max2 = 0
    for child in tree[node]:
        if child == parent:
            continue
        depth = dfs(child, node)
        if depth > max1:
            max2 = max1
            max1 = depth
        elif depth > max2:
            max2 = depth
    max_diameter = max(max_diameter, max1 + max2)
    return max1 + 1

dfs(1, -1)
print(max_diameter)

medium

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Build the tree and understand structure

   The tree edges form: 1-2-3, 2-4-5. The longest path is from node 3 to node 5 via 2 and 4.

2. Step 2: Calculate longest path length

   Path 3->2->4->5 has 3 edges, so diameter is 3 edges = 4 nodes in path length. The code counts edges, so max_diameter = 3 edges.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest path edges = 3 [OK]

Hint: Diameter = max sum of two largest depths at any node [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Ignoring parent check in DFS
• Mixing up max1 and max2 updates

4. The following code attempts to find the diameter of a tree but produces incorrect output. What is the bug?

def dfs(node, parent):
    max_depth = 0
    for child in tree[node]:
        if child != parent:
            depth = dfs(child, node)
            if depth > max_depth:
                max_depth = depth
    return max_depth + 1

max_diameter = 0
def find_diameter(node, parent):
    global max_diameter
    depths = []
    for child in tree[node]:
        if child != parent:
            depths.append(dfs(child, node))
    if len(depths) >= 2:
        depths.sort(reverse=True)
        max_diameter = max(max_diameter, depths[0] + depths[1])
    for child in tree[node]:
        if child != parent:
            find_diameter(child, node)

find_diameter(1, -1)
print(max_diameter)

medium

A. The recursive call to find_diameter is missing

B. max_diameter is not updated globally

C. Sorting depths in descending order is incorrect

D. Only updates max_diameter when len(depths) >= 2, missing updates for nodes with fewer than 2 children

Solution

1. Step 1: Identify the conditional update bug

   The code only updates max_diameter if len(depths) >= 2, but to mimic standard algorithm, it should always update using the two largest depths (with second as 0 if fewer children).

2. Step 2: Understand impact on chain trees

   In chain trees, nodes often have at most 1 child (excluding parent), so the condition skips updates, leaving max_diameter = 0 incorrectly.

3. Final Answer:

   Only updates max_diameter when len(depths) >= 2, missing updates for nodes with fewer than 2 children -> Option D

4. Quick Check:

   Pad missing depths with 0 for diameter update [OK]

Hint: Always update diameter with top two downward depths (pad 0 if needed) [OK]

Common Mistakes:

• Not updating global max_diameter
• Incorrect sorting order of depths
• Missing recursive calls in diameter function

5. You want to find the diameter of a weighted tree where edges have different lengths. Which modification to the standard DP on trees diameter algorithm is correct? A weighted tree is represented as adjacency list with tuples (neighbor, weight).

tree = {
  1: [(2, 3), (3, 2)],
  2: [(1, 3), (4, 4)],
  3: [(1, 2)],
  4: [(2, 4)]
}

# Which code snippet correctly computes diameter?

hard

A. Use BFS twice ignoring weights to find diameter

B. Use dfs to return max weighted depth, update diameter by sum of top two weighted depths

C. Ignore weights and count edges only for diameter

D. Sum all weights in the tree and divide by 2

Solution

1. Step 1: Understand weighted tree diameter

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

2. Step 2: Modify DFS to return max weighted depth and update diameter

   DFS returns max weighted depth from node; diameter updated by sum of two largest weighted depths.

3. Final Answer:

   Use dfs to return max weighted depth, update diameter by sum of top two weighted depths -> Option B

4. Quick Check:

   Weighted diameter = sum of max weighted depths [OK]

Hint: Include edge weights in depth sums for weighted diameter [OK]

Common Mistakes:

• Ignoring weights and treating as unweighted
• Using BFS without weights for weighted diameter
• Summing all weights instead of longest path