# Finding the diameter of a N-ary tree graph, without using BFS

As the title hints, I'm looking for a dynamic programming/greedy approach to find the diameter of a N-ary tree graph.

This must be done in linear time.

The problem states that the graph is undirected when passed to the algorithm, yet there is a way to transform it into a rooted directed tree graph in linear time.

All the solutions I've seen are using DFS in combination with a dynamic programming-ish approach to solve in linear time, yet I was wondering if there is a purely DP/greedy apporach which will yield linear time?

I've tried to approach this in several ways but it always comes down to either a double BFS algorithm, or DP using DFS.

An algorithm that came to mind:

1. randomly choose a vertex (x), transform the undirected tree into a rooted directed tree
2. give each node it's distance from x , also remember the node with max distance (y).
3. transform the tree to be rooted from y
4. perform step 2 on y, save the new max in z
5. return distance between y and z


This algorithm will run in $$O(n)$$, I'm just not sure this implements some (or if any) sort of dp/greedy logic, plain tree traversal.

• Could you motivate the reason why you don't want to use a (perfectly correct and efficient) BFS? Commented Nov 26, 2022 at 11:34
• This is part of a problem sheet I'm solving, unfortunately I'm constrained to solving using only dynamic programming/greedy approaches. Commented Nov 26, 2022 at 11:37