CODEWITHSUNDEEP
c++data-structuresgraph-theorygraph-algorithmdepth-first-search
Ayush Gupta
Ayush Gupta

Reputation: 37

Runtime error in Largest Distance between nodes of a Tree

This is an interviewbit.com problem : https://www.interviewbit.com/problems/largest-distance-between-nodes-of-a-tree/

Given an arbitrary unweighted rooted tree which consists of N (2 <= N <= 40000) nodes. The goal of the problem is to find largest distance between two nodes in a tree. Distance between two nodes is a number of edges on a path between the nodes (there will be a unique path between any pair of nodes since it is a tree). The nodes will be numbered 0 through N - 1.

I am finding a node which is farthest from root node using dfs. From this node i am doing DFS to find the farthest node. this distance is the required answer. I implemented it, but while calling do_dfs function i am getting segmentation fault. i wrote return statement after every line to find out where i am getting error. I have indicated that line in comment in code.

pair<int,int> do_dfs(vector<vector<int>> &adj, int n, int root)
{
    int l1 = 0;
    stack<pair<int,int>> st;
    st.push(make_pair(root,0));
    vector<int> vis(n,-1); 
    vis[root]=1;  //This statement is causing segmentation fault
    int longest=-1;

    while(!st.empty())
    {
        int top=st.top().first , l=st.top().second;
        int x=-1;
        for(int i=0;i<adj[top].size();++i)
        {
            int node = adj[top][i];
            if(vis[node] ==-1)
            {
                x = node;
                st.push(make_pair(node,l+1));
                vis[node]=1;
                break;
            }
        }

        if(x==-1)
        {
            if(l>l1)
            {
                l1 = l;
                longest = top;

            }
            st.pop();
        }
    }
    return make_pair(longest,l1);
}


int Solution::solve(vector<int> &A) 
{
    if(A.size()<3)return (A.size()-1);

    vector<vector<int>> adj(A.size());
    int root;
    for(int i=1;i<A.size();++i)
    {
        if(A[i]==-1)
        {
            root = i;
            continue;
        }
        adj[i].push_back(A[i]);
        adj[A[i]].push_back(i);
    }
    //adjacent list for graph complete

    pair<int,int> d1=do_dfs(adj,A.size(),root) ;
    pair<int,int> d2 = do_dfs(adj, A.size(), d1.first);
    int ans = d2.second;
    return ans;
}

Tescases :- A : [ -1, 0, 0, 1, 2, 1, 5 ] expected output : 5

A : [ -1, 0, 0, 0, 3 ] expected output : 3

Upvotes: 1

Views: 467

Answers (1)

Robur_131
Robur_131

Reputation: 372

Change the line in Solution::solve(vector<int> &A):

for(int i = 1 ; i < A.size() ; ++i)

To:

for(int i = 0; i < A.size() ; ++i)

And your problem gets solved.

The problem is you're not fully iterating the given A array. You start iterating from the index 1, while the array goes from index 0 to A.size() - 1. So your adjacency list does not get constructed properly, and the root variable remains uninitialized in some cases. So you run into Runtime error.

Upvotes: 3

Related Questions