# Finding n farthest leaves in a tree

Given a tree $$T$$, I want to find a subset $$N$$ of $$n$$ leaves that are farthest apart. I.e., I want to find $$N$$ that maximizes function:

$$f(N)=\sum\limits_{x_1,x_2 \in N, x_1 \neq x_2}{dist(x_1,x_2)}$$

where $$dist(x_1, x_2)$$ is the number of edges in a path between two vertices/nodes $$x_1$$ and $$x_2$$.

What algorithm can I use?

## 1 Answer

If you have a binary tree, you should be able to solve this using dynamic programming.

Let $$A[v,j,k]$$ denote the maximum possible value of the objective function

$$f'(N) = \sum_{x_1,x_2 \in N} \text{dist}(x_1,x_2) + k \sum_{x \in N} \text{dist}(v,x)$$

where $$N$$ ranges over all subsets of exactly $$j$$ leaves from among those that are descendants of $$v$$ (i.e., leaves of the subtree rooted at $$v$$).

If $$v$$ is a leaf, it is easy to compute $$A[v,j,k]$$ for all $$j,k$$.

If $$v$$ has one child $$v'$$, it is easy to compute $$A[v,j,k]$$ for all $$j,k$$ from $$A[v',\cdot,\cdot]$$.

So now suppose $$v$$ has two children $$v',v''$$. Then we can work out a recursive equation for $$A[v,j,k]$$ in terms of values $$A[w,\cdot,\cdot]$$ where the $$w$$'s are descendants of $$v$$:

$$A[v,j,k] = \max A[v',j',k+j''] + A[v'',j'',k+j'] + 2 j' j'' + jk$$

where $$j',j''$$ range over all values such that $$j'+j'' = j$$, $$0 \le j',j'' \le j$$. The intended meaning is that $$j'$$ counts the number of leaves in $$N$$ that are descendants of $$v'$$ and $$j''$$ counts the number of leaves in $$N$$ that are descendants of $$v''$$. In other words, we split $$N=N' \cup N''$$ where $$N'$$ contains $$j'$$ leaves from the descendants of $$v'$$, and $$N''$$ contains $$j''$$ leaves from the descendants of $$v''$$; then (loosely speaking) we compute the maximum value of $$f'(N)$$ in terms of the maximum values of $$f'(N')$$ and $$f'(N'')$$. The $$2jj'$$ term counts distances of the form $$\text{dist}(x_1,x_2)$$ where $$x_1 \in N'$$ and $$x_2 \in N''$$. The $$jk$$ term accounts for the fact that the $$j$$ root-to-leaf paths all need to be extended by one edge (thank you @j_random_hacker).

If you have an arbitrary tree (not necessarily a binary tree), you can convert it to a binary tree as follows: whenever you have a node $$v$$ with $$m$$ children, create a little binary tree with $$m$$ leaves, then put $$v$$ at the root of that binary tree and paste the children of $$v'$$ in at its $$m$$ leaves. Put a distance of 0 on all the edges of that new little binary tree except the top level. Repeat recursively.

In this way you obtain a binary tree where every edge has a distance of either 0 or 1 on it, and the distance between two vertices $$v,w$$ is the sum of the distances on the edges in the path between $$v$$ and $$w$$. Now you should be able to generalize the above algorithm to that case. I'll let you handle the details.

• @dzieciou, Thank you, those are excellent points, my answer had some errors in it. See revised answer. Please review carefully; it might well have other errors as well. – D.W. Jan 17 at 20:39
• Nice approach! I think that there needs to be an additional $jk$ term in the recursion formula though, to account for the fact that the $j$ leaf-to-$v$ paths that the 2 subproblem solutions refer to all need to be extended by 1 weight-$k$ edge. – j_random_hacker Jan 18 at 12:36
• Thanks for revising the answer. One more note as I'm not sure if I understood your approach for converting arbitrary trees to binary ones. I've drawn an example. Here children from the original tree are always encoded as a left child in binary tree and edges to left childs have weight 1. Remaining edges (those to right children) have 0 weight. I thought about using Wikipedia procedure for encoding m-trees as binary trees, but it changes some leaves into internal nodes. – dzieciou Jan 18 at 18:25
• @j_random_hacker, ooh, good point! Fixed. – D.W. Jan 18 at 20:03
• @dzieciou, yup, that looks like it should work! (I was imagining something slightly different but yours should work just as well.) – D.W. Jan 18 at 20:04