Finding The Longest path in a tree using DFS

#include<iostream>
#include<list>
#include<vector>
#include<stack>

using namespace std;

class Tree {

    private:

        int nodes;  // Nodes in a tree
        int node_farthest_from_root; // Node farthest from the root node
        int max_path_length; // To store the length of the longest path
        int length; // Length calculated at the current node
        int start_node, end_node; // The start and end nodes of the longest path
        list<int> *adjlist;
        vector<bool> visited;
        vector<int> longest_path; // Store the longest path from the start_node till the end_node
        
    public:

        Tree () {
        }

        Tree (int nodes) { // Allocate resources 
            max_path_length = 0;  
            node_farthest_from_root = 0;
            length = 0;
            adjlist = new list<int> [nodes];
            visited.resize(nodes, false);
            this->nodes = nodes;
        }

        ~Tree(){ // Free allocated resources
            delete [] adjlist;
        }

        void AddEdge (int src, int dst) {
            adjlist[src].push_back(dst);
            adjlist[dst].push_back(src);
        }
         
        /* Below DFS function finds 
           1. The length of the longest path from the source node.
           2. The node farthest from the source node.
        */
        void DFS_GoFarthest (int src) {

            visited[src] = true;
            for (auto& itr : adjlist[src]) {
                if (!visited[itr]) {
                    length++;
                    DFS_GoFarthest(itr);
                    length--;
                }
            }
            if (length > max_path_length) {
                max_path_length = length;
                node_farthest_from_root = src;
            }
        }

        /* Below DFS function
           1. Finds the longest path from the start node to the end node.
        */
        void DFS_FindPath (int src) {

            visited[src] = true;
            for (auto& itr : adjlist[src]) {
                if (!visited[itr]) {
                    longest_path.push_back(itr);
                    if (itr == end_node) {
                        for (auto& it : longest_path) {
                            cout << it << " ";
                        } 
                        max_path_length = longest_path.size();
                        return ;
                    }
                    DFS_FindPath(itr);
                    longest_path.pop_back();
                }
            }
        }

        // Mark nodes unvisited for next traversal
        void MarkUnvisited () {
            fill(visited.begin(), visited.end(), false);
        }

        void Reset_PathLengths () {
            length = 0;
            max_path_length = 0;
        }

        int Get_FarthestNode () {
            return node_farthest_from_root;
        }
      
        int Get_LenghtOfLongestPath () {
            return max_path_length;
        }

        void Set_StartAndEndNode (int arg_start_node, int arg_end_node) {
            start_node = arg_start_node;
            end_node   = arg_end_node;
            longest_path.push_back(start_node);
        }
};

int main() 
{
    Tree t(16);

    // Add edges to the tree
    t.AddEdge(0,1);
    t.AddEdge(0,2);
    t.AddEdge(0,3);
    t.AddEdge(1,4);
    t.AddEdge(1,5);
    t.AddEdge(1,6);
    t.AddEdge(3,7);
    t.AddEdge(3,8);
    t.AddEdge(4,9);
    t.AddEdge(7,11);
    t.AddEdge(9,10);
    t.AddEdge(11,12);
    t.AddEdge(11,13);
    t.AddEdge(11,14);
    t.AddEdge(14,15);

    int start_node, end_node;

    // Find the node farthest from the root node i.e from node 0.
    t.DFS_GoFarthest(0);

    // Node farthest from the root will be the start node.
    start_node = t.Get_FarthestNode();

    // Mark the nodes unvisited for another DFS traversal.
    t.MarkUnvisited();

    // Once the node farthest from the root node is found, reset the max_path_length
    t.Reset_PathLengths();

    // Find the farthest node from the start node (farthest_node_from_root).
    t.DFS_GoFarthest(start_node);

    // Node farthest from the start node will be the end node.
    end_node = t.Get_FarthestNode();

    // Set the start node and the end node in the tree.
    t.Set_StartAndEndNode(start_node, end_node);
    
    cout << "Starting node : " << start_node << endl; 
    cout << "Ending node   : " << end_node << endl;

    // Mark the nodes unvisited for another DFS traversal.
    t.MarkUnvisited();

    // Find the path from the start node to the end node.
    cout << "Longest Path : ";
    t.DFS_FindPath(start_node);

    cout << endl << "Length of the longest path : " << t.Get_LenghtOfLongestPath() << " nodes." << endl;
 
    return 0;
}

Starting node : 15
Ending node   : 10
Longest Path : 15 14 11 7 3 0 1 4 9 10
Length of the longest path : 10 nodes.

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Tree{

    private int nodes;  // Nodes in a tree
    private int node_farthest_from_root; // Node farthest from the root node
    private int max_path_length; // To store the length of the longest path
    private int length; // Length calculated at the current node
    private int start_node, end_node; // The start and end nodes of the longest path
    private List<List<Integer>> adjlist; // Adjacency list to store the graph
    private boolean visited[];
    private List<Integer> longest_path; // Store the longest path from the start_node till the end_node
        
    Tree () {
    }

    Tree (int arg_nodes) { // Allocate resources

        nodes = arg_nodes;
        max_path_length = 0;
        node_farthest_from_root = 0;
        length = 0;

        adjlist = new ArrayList<>(nodes);
        for (int i=0; i<nodes; i++)
            adjlist.add(new ArrayList<>());

        visited = new boolean[nodes];
        longest_path = new ArrayList<>();
    }

    public void AddEdge (int src, int dst) {
        adjlist.get(src).add(dst);
        adjlist.get(dst).add(src);
    }
     
    /* Below DFS function finds
       1. The length of the longest path from the source node.
       2. The node farthest from the source node.
    */
    public void DFS_GoFarthest (int src) {

        visited[src] = true;
        for (Integer adj_node : adjlist.get(src)) {
            if (!visited[adj_node]) {
                length++;
                DFS_GoFarthest(adj_node);
                length--;
            }
        }
        if (length > max_path_length) {
            max_path_length = length;
            node_farthest_from_root = src;
        }
    }

    /* Below DFS function
       1. Finds the longest path from the start node to the end node.
    */
    public void DFS_FindPath (int src) {

        visited[src] = true;
        for (Integer adj_node : adjlist.get(src)) {
            if (!visited[adj_node]) {
                longest_path.add(adj_node);
                if (adj_node == end_node) {
                    for (Integer node : longest_path) {
                        System.out.print(node + " ");
                    }
                    max_path_length = longest_path.size();
                    return;
                }
                DFS_FindPath(adj_node);
                longest_path.remove(longest_path.size()-1);
            }
        }
    }

    // Mark nodes unvisited for next traversal
    public void MarkUnvisited () {
        Arrays.fill(visited, false);
    }

    public void Reset_PathLengths () {
        length = 0;
        max_path_length = 0;
    }

    public int Get_FarthestNode () {
        return node_farthest_from_root;
    }
    
    public int Get_LenghtOfLongestPath () {
        return max_path_length;
    }

    public void Set_StartAndEndNode (int arg_start_node, int arg_end_node) {
        start_node = arg_start_node;
        end_node   = arg_end_node;
        longest_path.add(start_node);
    }

    public static void main(String args[]) {

        Tree t = new Tree(16);
    
        // Add edges to the tree
        t.AddEdge(0,1);
        t.AddEdge(0,2);
        t.AddEdge(0,3);
        t.AddEdge(1,4);
        t.AddEdge(1,5);
        t.AddEdge(1,6);
        t.AddEdge(3,7);
        t.AddEdge(3,8);
        t.AddEdge(4,9);
        t.AddEdge(7,11);
        t.AddEdge(9,10);
        t.AddEdge(11,12);
        t.AddEdge(11,13);
        t.AddEdge(11,14);
        t.AddEdge(14,15);
    
        int start_node, end_node;
    
        // Find the node farthest from the root node i.e from node 0.
        t.DFS_GoFarthest(0);
    
        // Node farthest from the root will be the start node.
        start_node = t.Get_FarthestNode();
    
        // Mark the nodes unvisited for another DFS traversal.
        t.MarkUnvisited();
    
        // Once the node farthest from the root node is found, reset the max_path_length
        t.Reset_PathLengths();
    
        // Find the farthest node from the start node that was found earlier.
        // (start node is the farthest_node_from_root).
        t.DFS_GoFarthest(start_node);
    
        // Node farthest from the start node will be the end node.
        end_node = t.Get_FarthestNode();
    
        // Set the start node and the end node in the tree.
        t.Set_StartAndEndNode(start_node, end_node);
        
        System.out.println("Starting node : " + start_node); 
        System.out.println("Ending node   : " + end_node);
    
        // Mark the nodes unvisited for another DFS traversal.
        t.MarkUnvisited();
    
        // Find the path from the start node to the end node.
        System.out.print("Longest Path : ");
        t.DFS_FindPath(start_node);
    
        System.out.print("\nLength of the longest path : " + t.Get_LenghtOfLongestPath() + " nodes.");
    }
}

Starting node : 15
Ending node   : 10
Longest Path : 15 14 11 7 3 0 1 4 9 10
Length of the longest path : 10 nodes.