How to find longest path in a non-binary tree and return it in a vector?

Question

I have a problem where I need to find the longest path in a non-binary tree structure. I don't want to return the size of the longest path, I want to return the elements of the longest path in a vector. For example, in a following picture 1 I want to find the longest path and store it in a vector like this: {A,B,D,I,L}. I think recursion is a way to go, but I just can't get the idea how to start building the code around the problem. I am storing the nodes in a following structures:

std::unordered_map<std::string ID, Node> Node_data_;
struct Node
{
    
std::string id;

Name name;
    
std::vector<Node*> children;
    
Town_info* master = nullptr;

};

Jack Tang Jack Tang · Accepted Answer · 2021-11-20T04:33:13

I can't comment because I have under 50 points. Also this naive solution is pretty naive, lol.

But after you have achieved the longest length, why not just run the algorithm again, but this time with a count of the length, and if the accumulative length is equal to max length, it means you have found the right path, from then, just end at that.

bool recur(node_info, int length, int std::vector<std::string>& vs) {

    ...
    if(length == max_length) {
        return true;
    }
    for (neighbour nodes of this current node)
    {
        bool haveFound = recur(next_node,length + next_node_length, vs);
            if(haveFound) {
                vs.push_back(next_node);
                return true;
            }
    }
}

You can modify the code so that it not only stops at the first maximal length it finds, but keep exhausting all nodes in the tree.

How to find longest path in a non-binary tree and return it in a vector?

1 Answers