# Finding The Longest path in a tree using DFS

The logic behind finding the longest path in a tree (diameter of a tree) using Depth First Search (DFS) is as below
a)    Traverse from the root node and find the farthest node from it using Depth First Search (DFS).
b)    Treat the farthest node from the root as the start node.
c)    Traverse from the start node and reach the farthest node using Depth First Search (DFS). The farthest node is the end node of the longest path.

Note: To print the actual path from the start node till the end node, we can do another DFS traversal.

Example

Program for finding the longest path in a tree

``````#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
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;
visited.resize(nodes, false);
this->nodes = nodes;
}

~Tree(){ // Free allocated resources
}

void AddEdge (int src, int dst) {
}

/* 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

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;
}
``````

Output

``````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 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;

for (int i=0; i<nodes; i++)

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

public void AddEdge (int src, int dst) {
}

/* 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;
length++;
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 node : longest_path) {
System.out.print(node + " ");
}
max_path_length = longest_path.size();
return;
}
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;
}

public static void main(String args[]) {

Tree t = new Tree(16);

// Add edges to the tree

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.");
}
}
``````

Output

``````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.
``````