DP on Trees Diameter of Tree in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of diameter calculation on a simple tree

What is the output of the following C++ code that calculates the diameter of a tree using DP on trees?

DSA C++

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

vector<vector<int>> tree;
int diameter = 0;

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

int main() {
    int n = 5;
    tree.resize(n);
    tree[0].push_back(1); tree[1].push_back(0);
    tree[1].push_back(2); tree[2].push_back(1);
    tree[1].push_back(3); tree[3].push_back(1);
    tree[3].push_back(4); tree[4].push_back(3);

    dfs(0, -1);
    cout << diameter << endl;
    return 0;
}

A 2

B 4

C 3

D 5

💡 Hint

Trace the longest path between any two nodes in the tree.

The longest path (diameter) in the tree is from node 2 to node 4 passing through nodes 1 and 3, which has length 4 edges.

🧠 Conceptual

intermediate

Understanding diameter calculation logic

In the DP on trees approach to find the diameter, what do the two maximum depths (max1 and max2) represent in the DFS function?

A The two longest depths from the current node to its descendants

B The two shortest paths from the root to the current node

C The depths of the current node's parent and grandparent

D The number of children and grandchildren of the current node

💡 Hint

Think about how the diameter is formed by combining two longest paths through a node.

max1 and max2 store the lengths of the two longest downward paths from the current node to its descendants, which help compute the diameter passing through this node.

🔧 Debug

advanced

Identify the error causing wrong diameter output

The following code attempts to compute the diameter of a tree but outputs 3 instead of 4. What is the error?

DSA C++

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

vector<vector<int>> tree;
int diameter = 0;

int dfs(int node, int parent) {
    int max1 = 0, max2 = 0;
    for (int child : tree[node]) {
        if (child == parent) continue;
        int 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;
}

int main() {
    int n = 5;
    tree.resize(n);
    tree[0].push_back(1); tree[1].push_back(0);
    tree[1].push_back(2); tree[2].push_back(1);
    tree[1].push_back(3); tree[3].push_back(1);
    tree[3].push_back(4); tree[4].push_back(3);

    dfs(0, -1);
    cout << diameter << endl;
    return 0;
}

A The depth returned should be incremented by 1 after recursion, not before

B The depth returned should be incremented by 1 before recursion

C The diameter update should use max1 + max2 + 1 instead of max1 + max2

D The diameter variable should be reset inside the dfs function

💡 Hint

Check where the +1 is added to the depth returned by recursive calls.

The code returns depth without adding 1 after recursion, so max1 and max2 are off by one, causing diameter to be smaller by 1.

📝 Syntax

advanced

Identify the syntax error in diameter calculation code

Which option contains a syntax error that prevents the code from compiling?

DSA C++

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

A Using 'continue' inside for loop is invalid syntax

B The variable 'diameter' is not declared

C Missing semicolon after 'int depth = dfs(child, node) + 1'

D The return statement must return max1 + max2 instead of max1

💡 Hint

Look carefully at the line where depth is assigned.

The line 'int depth = dfs(child, node) + 1' is missing a semicolon at the end, causing a syntax error.

🚀 Application

expert

Calculate diameter of a weighted tree using DP on trees

Given the weighted tree below, what is the diameter (maximum sum of edge weights on any path)? Edges: 0 - 1 (weight 3) 1 - 2 (weight 4) 1 - 3 (weight 2) 3 - 4 (weight 6) Use the DP on trees approach where dfs returns the maximum weighted path from node to descendants.

DSA C++

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

struct Edge {
    int to, weight;
};

vector<vector<Edge>> tree;
int diameter = 0;

int dfs(int node, int parent) {
    int max1 = 0, max2 = 0;
    for (auto &edge : tree[node]) {
        if (edge.to == parent) continue;
        int depth = dfs(edge.to, node) + edge.weight;
        if (depth > max1) {
            max2 = max1;
            max1 = depth;
        } else if (depth > max2) {
            max2 = depth;
        }
    }
    diameter = max(diameter, max1 + max2);
    return max1;
}

int main() {
    int n = 5;
    tree.resize(n);
    tree[0].push_back({1, 3}); tree[1].push_back({0, 3});
    tree[1].push_back({2, 4}); tree[2].push_back({1, 4});
    tree[1].push_back({3, 2}); tree[3].push_back({1, 2});
    tree[3].push_back({4, 6}); tree[4].push_back({3, 6});

    dfs(0, -1);
    cout << diameter << endl;
    return 0;
}

A 15

B 16

C 14

D 13

💡 Hint

Find the longest weighted path between any two nodes by combining two longest weighted paths from a node.

The longest weighted path is 2 -> 1 -> 3 -> 4 with weights 4 + 2 + 6 = 12. The diameter is 13 because at node 1, max1 is 8 (path to 4 via 3) and max2 is 5 (path to 2), sum is 13.

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