Two-BFS Implementation

Here is the two-BFS implementation:

function bfs(start, adj, n):
    dist = array of size n + 1, all -1
    dist[start] = 0
    q = queue with start
    farthest = start

    while q is not empty:
        u = q.pop()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.push(v)
                if dist[v] > dist[farthest]:
                    farthest = v

    return (farthest, dist[farthest])

function treeDiameter(adj, n):
    (a, _) = bfs(1, adj, n)
    (b, diameter) = bfs(a, adj, n)
    return diameter

Both BFS runs look identical. You are running the same code twice with different starting points.

This runs in $O(n)$ time and uses $O(n)$ space.