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

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

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

Copyright (c) 2019-2022, Algotree.org.
All rights reserved.