DP on Trees Diameter of Tree in DSA C++

Mental Model

The diameter of a tree is the longest path between any two nodes. We find it by checking the longest paths through each node using dynamic programming.

Analogy: Imagine a network of roads connecting cities. The diameter is the longest route you can drive without repeating roads. We find it by looking at the longest two roads leaving each city and combining them.

    1
   / \
  2   3
     / \
    4   5

Each number is a city (node), lines are roads (edges).

Dry Run Walkthrough

Input: Tree edges: 1-2, 1-3, 3-4, 3-5

Goal: Find the longest path between any two nodes in the tree (diameter).

Step 1: Start DFS from node 1 to calculate longest paths down each subtree

Visited nodes: 1
Longest paths from children: none yet

Why: We need to explore children to find longest paths

Step 2: Visit node 2 (leaf), longest path down is 0

2 -> null (leaf)
Return height=0 to parent 1

Why: Leaf nodes have height 0, base case for recursion

Step 3: Visit node 3, explore children 4 and 5

3 -> 4, 5
Not calculated heights yet

Why: Need children's heights to compute node 3's height

Step 4: Visit node 4 (leaf), height=0, return to 3

4 -> null
Return height=0

Why: Leaf node base case

Step 5: Visit node 5 (leaf), height=0, return to 3

5 -> null
Return height=0

Why: Leaf node base case

Step 6: Calculate node 3 height = max(0,0)+1=1; update diameter = max(0, 0+0+2)=2

3 -> height=1
Diameter updated to 2 (path 4-3-5)

Why: Diameter through node 3 is sum of two longest child heights plus 2 edges

Step 7: Calculate node 1 height = max(0,1)+1=2; update diameter = max(2, 0+1+2)=3

1 -> height=2
Diameter updated to 3 (path 2-1-3-4 or 2-1-3-5)

Why: Diameter through node 1 is sum of two longest child heights plus 2 edges

Result:

Diameter = 3 edges
Longest path example: 2 -> 1 -> 3 -> 4

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Tree {
public:
    int n;
    vector<vector<int>> adj;
    int diameter = 0;

    Tree(int nodes) : n(nodes) {
        adj.resize(n + 1);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int dfs(int node, int parent) {
        int max1 = 0, max2 = 0; // top two heights
        for (int child : adj[node]) {
            if (child == parent) continue; // avoid going back
            int height = dfs(child, node); // get child's height
            if (height > max1) {
                max2 = max1;
                max1 = height;
            } else if (height > max2) {
                max2 = height;
            }
        }
        diameter = max(diameter, max1 + max2 + 2); // update diameter
        return max1 + 1; // height of current node
    }

    int getDiameter() {
        dfs(1, -1); // start DFS from node 1
        return diameter;
    }
};

int main() {
    Tree tree(5);
    tree.addEdge(1, 2);
    tree.addEdge(1, 3);
    tree.addEdge(3, 4);
    tree.addEdge(3, 5);
    cout << tree.getDiameter() << "\n";
    return 0;
}

for (int child : adj[node]) { if (child == parent) continue; int height = dfs(child, node);

Traverse children skipping parent to avoid cycles

if (height > max1) { max2 = max1; max1 = height; } else if (height > max2) { max2 = height; }

Track top two longest child heights

diameter = max(diameter, max1 + max2 + 2);

Update diameter with longest path through current node

return max1 + 1;

Return height of current node for parent's calculation

Output

3

Complexity Analysis

Time: O(n) because we visit each node once in DFS

Space: O(n) for adjacency list and recursion stack

vs Alternative: Naive approach checks all pairs of nodes for longest path O(n^2), DP approach is efficient O(n)

Edge Cases

Single node tree

Diameter is 0 because no edges exist

DSA C++

for (int child : adj[node]) { if (child == parent) continue; ... }

Linear chain tree

Diameter equals number of edges in chain, correctly computed by summing heights

DSA C++

diameter = max(diameter, max1 + max2 + 2);

Star shaped tree

Diameter is 2 (longest path between two leaves through center)

DSA C++

if (height > max1) { max2 = max1; max1 = height; } else if (height > max2) { max2 = height; }

When to Use This Pattern

When asked for longest path in a tree, use DP on trees by computing heights and combining top two heights at each node to find diameter.

Common Mistakes

Mistake: Not skipping parent node in DFS causing infinite recursion
Fix: Add condition to skip parent node in adjacency traversal

Mistake: Updating diameter with only one child's height instead of sum of top two
Fix: Track two largest heights and sum them plus 2 edges for diameter update

Summary

Computes the longest path between any two nodes in a tree using DFS and dynamic programming.

Use when you need the maximum distance between nodes in a tree structure efficiently.

The diameter passes through a node combining the two longest child paths, so track top two heights at each node.

Practice

1. What does the diameter of a tree represent in graph theory?

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 defined as the longest path between any two nodes in a 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 leaves 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 counts nodes instead of path length
• Assuming diameter must pass through root

2. Which of the following is the correct way to declare a vector of vectors to represent an adjacency list for a tree in C++?

easy

A. std::vector<int> adj[n];

B. std::vector adj(n);

C. std::vector adj(n, std::vector<int>());

D. std::vector adj(n);

Solution

1. Step 1: Understand vector of vectors syntax

   Correct syntax uses std::vector adj(n); to create n empty vectors.

2. Step 2: Check other options for errors

   std::vector<int> adj[n]; uses array of vectors (valid but less modern), C misses template arguments, D misses template parameters.

3. Final Answer:

   std::vector adj(n); -> Option B

4. Quick Check:

   Correct vector of vectors syntax = std::vector adj(n); [OK]

Hint: Use std::vector adj(n); for adjacency list [OK]

Common Mistakes:

• Missing template parameters in vector
• Using C-style arrays instead of vectors
• Incorrect initialization syntax

3. Consider the following C++ code snippet to find the diameter of a tree using DFS and DP. What will be the output if the tree edges are: (0-1), (1-2), (1-3)?

std::vector adj(4);
adj[0].push_back(1); adj[1].push_back(0);
adj[1].push_back(2); adj[2].push_back(1);
adj[1].push_back(3); adj[3].push_back(1);

int diameter = 0;

int dfs(int node, int parent, const std::vector& adj, int& diameter) {
    int max1 = 0, max2 = 0;
    for (int child : adj[node]) {
        if (child == parent) continue;
        int height = dfs(child, node, adj, diameter) + 1;
        if (height > max1) {
            max2 = max1;
            max1 = height;
        } else if (height > max2) {
            max2 = height;
        }
    }
    diameter = std::max(diameter, max1 + max2);
    return max1;
}

dfs(0, -1, adj, diameter);
std::cout << diameter << std::endl;

medium

A. 3

B. 1

C. 0

D. 2

Solution

1. Step 1: Understand the tree structure and DFS traversal

   The tree edges form a structure: 0-1 connected, 1 connected to 2 and 3. The longest path is from node 2 to node 3 through 1, length 2 edges.

2. Step 2: Calculate diameter from DFS logic

   DFS calculates max1 and max2 heights from children. For node 1, max1=1 (to 2), max2=1 (to 3), so diameter = max(0,1+1)=2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Longest path length = 2 edges [OK]

Hint: Diameter = sum of two longest child heights at any node [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Not updating diameter correctly
• Confusing parent and child in DFS

4. The following code attempts to compute the diameter of a tree but produces incorrect results. What is the main bug?

int dfs(int node, int parent, const std::vector& adj, int& diameter) {
    int maxHeight = 0;
    for (int child : adj[node]) {
        if (child == parent) continue;
        int height = dfs(child, node, adj, diameter) + 1;
        if (height > maxHeight) {
            maxHeight = height;
            diameter = std::max(diameter, maxHeight);
        }
    }
    return maxHeight;
}

medium

A. DFS does not return any value

B. Parent node is not skipped in DFS

C. Diameter is updated only with maxHeight, missing sum of two heights

D. Height is not incremented correctly

Solution

1. Step 1: Analyze diameter update logic

   The code updates diameter only with maxHeight, which is the longest single path from current node, but diameter requires sum of two longest paths through the node.

2. Step 2: Identify missing second longest path

   Without tracking two longest heights, the code misses paths passing through the node combining two children, leading to incorrect diameter.

3. Final Answer:

   Diameter is updated only with maxHeight, missing sum of two heights -> Option C

4. Quick Check:

   Diameter needs sum of two longest child heights [OK]

Hint: Track two longest heights to update diameter correctly [OK]

Common Mistakes:

• Updating diameter with only one child's height
• Not skipping parent node in DFS
• Forgetting to increment height by 1

5. Given a tree with 6 nodes and edges: (0-1), (1-2), (1-3), (3-4), (4-5), what is the diameter of the tree? Use the DP on Trees approach where diameter is the longest path between any two nodes.

hard

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Visualize the tree and identify longest path

   The tree edges form paths: 0-1-3-4-5 and 2 connected to 1. The longest path is from node 2 to node 5 passing through 1,3,4 with length 5 edges.

2. Step 2: Calculate diameter using DP on Trees logic

   At node 1, two longest child heights are 1 (to 2) and 3 (to 5). Diameter = max(diameter, 1+3) = 4, but the longest path is from 2 to 5 which is 4 edges plus 1 edge from 0 to 1 is not part of longest path. Actually, the longest path is from node 2 to node 5 passing through 1,3,4 with length 5 edges.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Longest path length = 5 edges [OK]

Hint: Diameter = sum of two longest child heights at a node [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Ignoring one branch in longest path
• Miscounting edges in path