Linear time labeling algorithm for a tree?

Question

I have an undirected tree whose vertices I want to label. The leaf nodes should be labeled one. Then, assume the leaves were removed. In the tree that remains, the leaves should be labeled two. This process continues in the obvious way until all vertices have a label. The reason I do this is I want to store the vertices in a queue, and go through them "leaves first". Is there an easy way to do this $O(n+m)$ time?

I can solve the problem by doing a BFS on every step. But in the worst case, on every step I go through every vertex, remove exactly two leaves and enqueue them. I believe this takes quadratic time.

Another idea was to first find all the leaves, and then do a BFS from every leaf. This doesn't give me the desired solution. For example, consider a kind of "crown graph" as in the figure below. The desired solution is shown, but launching a BFS from each leaf would result in only two labels used.

Ideally, the linear time algorithm would also be easy to explain and implement.

Answer 1

Unrooted Trees

You can use a priority queue to solve this in $O(E+V\log V)$:

• Put all vertices in a priority queue, with their priority being their degree.
• While the queue is non-empty:
  • Remove a vertex $v$ of minimal priority, which must be $1$ (or $0$ at the very end).
  • Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
  • Subtract $1$ from the priority of the unique remaining neighbor of $u$ (if any).

In fact, we don't really need a priority queue, and this algorithm can be implemented using a simple queue in time $O(E+V)$:

• Initialize an array of length $V$ with the degrees of all vertices.
• Initialize another array of length $V$ with "alive".
• Go once through the first array, and push all vertices of degree $1$ to a queue.
• While the queue is non-empty:
  • Pop a vertex $v$.
  • Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
  • Mark $v$ as "dead".
  • If $v$ has some "alive" neighbor $u$, subtract $1$ from the degree of $u$.
  • If the new degree of $u$ is $1$, push $u$ to the queue.

Rooted Trees

Use DFS instead. Here is a sketch of the algorithm.

• Given a node $v$, if $v$ is a leaf, set $d(v) = 1$.
• If $v$ is not a leaf, run the algorithm on all its children, and then let $d(v) = 1 + \max d(u)$, where $u$ goes over the set of all children.

You run this algorithm on the root.

Answer 2

A straightforward answer is as follows:

• Turn this into a directed graph, where we have an edge $(u,v)$ from each node $u$ to its parent $v$. Note that you get a dag (directed acyclic graph).

• Topologically sort the graph.

• Scan the vertices, in sorted order. Label each vertex with one more than the largest of the labels on its predecessors. Since we're scanning in topological order, all of the predecessors of $v$ will already have received a label before we try to label $v$.

Each of these steps can be done in $O(n+m)$ time, so the total running time is $O(n+m)$. I mention this alternative approach only in case you find it conceptually easier to understand than Yuval's answer.