# C# - Find max distance leaves and path mid point - O(n)

• Find the farthest apart leaves on the tree. Do this by starting with any vertex and find it's farthest leaf. Then take that leaf and find the farthest vertex from it. Now you have the 2 farthest leaves on the tree. Find the path between them and take the middle 1 or 2 vertices depending on odd or even count in path.

``````    public IList<int> FindMinHeightTrees(int n, int[,] edges)
{
List<int>[] nodes = new List<int>[n];
for (int i = 0; i < n; i++) nodes[i] = new List<int>();

// build undirected graph
for (int i = 0; i < edges.GetLength(0); i++)
{
}

// Farthest() return value is 2 ints
//   int[0] - distance to farther node
//   int[1] - the farthest node
int[] leaf1 = Farthest(0, nodes, -1, 1); // start at any node
int[] leaf2 = Farthest(leaf1[1], nodes, -1, 1);  // farthest leaves

List<int> path = new List<int>();
FindPath(leaf1[1], nodes, -1, leaf2[1], path);

int mid = leaf2[0]/2;
IList<int> res = new List<int>() { path[mid] };
if (leaf2[0] % 2 == 0) res.Add(path[mid - 1]); // even length path has 2 middle nodes
return res;
}

public void FindPath(int node, List<int>[] nodes, int from, int end, List<int> path)
{
if (path.Count > 0 && path[path.Count - 1] == end) return;

foreach (int c in nodes[node])
{
if (c != from)
{
FindPath(c, nodes, node, end, path);
}
}

if (path[path.Count - 1] == end) return;
else path.RemoveAt(path.Count - 1);
}

// return value is 2 ints
//   int[0] - distance to farther node
//   int[1] - the farthest node
public int[] Farthest(int node, List<int>[] nodes, int from, int distance)
{
int[] max = new int[] { distance, node };
foreach (int c in nodes[node])
{
if (c != from)
{
int[] f = Farthest(c, nodes, node, distance + 1);
if (f[0] > max[0]) max = f;
}
}

return max;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.