The pseudocode below summarizes the neighbor-joining algorithm.

NeighborJoining(D,n) ifn = 2
T ← tree consisting of a single edge of length D_{1,2} return T D' ← neighbor-joining matrix constructed from the distance matrix D
find elements i and j such that D'_{i,j} is a minimum non-diagonal element of D'
Δ ← (TotalDistance_{D}(i) - TotalDistance_{D}(j)) /(n - 2) limbLength_{i} ← (1/2)(D_{i,j} + Δ) limbLength_{j}← (1/2)(D_{i,j} - Δ) add a new row/column m to D so that D_{k,m} = D_{m,k} = (1/2)(D_{k,i}+ D_{k,j} - D_{i,j}) for any k
remove rows i and j from D
remove columns i and j from D T ← NeighborJoining(D, n - 1)
add two new limbs (connecting node m with leaves i and j) to the tree T
assign length limbLength_{i} to Limb(i)
assign length limbLength_{j} to Limb(j) returnT

Neighbor Joining Problem

Construct the tree resulting from applying the neighbor-joining algorithm to a distance matrix.

Given: An integer n, followed by a space-separated n x n distance matrix.

Return: An adjacency list for the tree resulting from applying the neighbor-joining algorithm. Edge-weights should be accurate to two decimal places (they are provided to three decimal places in the sample output below).

Note on formatting: The adjacency list must have consecutive integer node labels starting from 0. The n leaves must be labeled 0, 1, ..., n-1 in order of their appearance in the distance matrix. Labels for internal nodes may be labeled in any order but must start from n and increase consecutively.