Trees, Find height of a tree has an error in the test cases

bug reports
,
1

I revised my code several times and discussed it with your AI

" You are likely correct. Given the problem statement and the numerous reviews of the code, the logic appears sound, and it’s highly probable that the test cases on CodeChef are flawed or have edge cases not explicitly covered in the problem description.

Given that:

  1. The tree is rooted at node 1.
  2. The input format specifies parent-child relationships.
  3. The dfs2 function correctly traverses the tree and calculates the depth.
  4. nodeDepth is correctly passed by reference.
  5. The initial parentDepth of -1 ensures the root node has a depth of 0.
  6. The height is updated correctly in dfs2.

Then, the code should function correctly for all valid test cases that conform to the problem description.

I recommend submitting the code as is. If it still fails, you can try to contact CodeChef support or discuss the problem in the CodeChef forums to see if there are any known issues with the test cases."

For some reason I am not able to debug to get the exact test case that fails.

image
image923×360 19.4 KB

Screenshot

My Code:

include <bits/stdc++.h>
using namespace std;

void dfs1(vector<vector> &tree, int node, int nodeDepth, int &maxDepth, vector &depth) {
// cout << "Visited " << node << ", Depth: " << nodeDepth << endl;
for (auto i: tree[node]) {
depth[i] = nodeDepth + 1;
dfs1(tree, i, nodeDepth + 1, maxDepth, depth);
}
if(tree[node].size() == 0) //leaf node
{
// cout << "Leaf Node, Max Depth: " << maxDepth << ", Node Depth: " << nodeDepth << endl;
maxDepth = std::max(maxDepth, nodeDepth);
}
}

void dfs2(vector<vector> &tree, int node, int &nodeDepth, int &maxDepth)
{
nodeDepth++;
maxDepth = std::max(maxDepth, nodeDepth);
for (auto i: tree[node])
{
dfs2(tree, i, nodeDepth, maxDepth);
}
nodeDepth–;
}

int main() {
// your code goes here
int N;
int n;
int height = 0;

cin >> N;
vector<vector<int>> tree(N + 1); //the nodes start at 1 not 0
vector<int> depth(N + 1); //the nodes start at 1 not 0

for(n = 0; n < N - 1; n++)
{
    int u, v;
    cin >> u >> v;
    tree[u].push_back(v);
}

// for(n = 1; n <= N; n++)
// {
//     cout << "Node: " << n << ", " << tree[n].size() << " Children: ";
//     for(auto &child : tree[n])
//     {
//         cout << child << " ";
//     }
//     cout << endl;
    
// }

// Start DFS from the root node
//dfs1(tree, 1, 0, height, depth);
int parentDepth = -1; //for the first node, there is no parent
dfs2(tree, 1, parentDepth, height);

cout << height;

}

2

The same happens with the Nodes at Kth Level exercise
Nodes at Kth Level in Trees and Binary trees