How to find maximum matching edges in undirected tree

Question

Let $B$ be an undirected tree with $|V|$ nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime $\mathcal{O}(|V|)$.

My approach:

Find all leaves. For each leaf if the parent edge has not been seen by another leaf, mark the edge to its parent as matching edge. Now delete all found leaves, its parents and the associated edges of the parents. Start over from the beginning.

Pseudo code:

graph = {
     1: [2, 3],
     2: [1, 4, 5],
     3: [1, 6],
     4: [2, 7, 8],
     5: [2, 9],
     6: [3],
     7: [4, 10, 11],
     8: [4, 12, 13],
     9: [5],
    10: [7, 14],
    11: [7],
    12: [8],
    13: [8, 15, 16],
    14: [10],
    15: [13],
    16: [13],
}
# example graph I used for testing purposes

while we haven't seen all nodes:
    leaves = [i for i in graph if len(graph[i]) == 1]
    seen += leaves
    for leaf in leaves:
        parent = graph[leaf][0]
        del graph[leaf]  # Throw away all leaves
        if not parent in seen:
            del graph[parent] # And throw away their parent
            matching_edges += [(leaf, parent)]
            seen += [parent]
            next_round_nodes += [parent]

But I'm afraid that is not linear, is it? Because first we look at $|V|$ and perform our algo. Then we do the same with $|V|-c$ leaves, where $c$ could actually be 2, if I understand that correctly, looking at graph which is a "line". So, really that seems quadratic.

TL;DR:

1. Is my algorithm correct?
2. What is the runtime?
3. If it is not linear, what other approach could I chose?

Answer 1

It is correct and runs in linear time. You can run a DFS to find the height and the parent node of each vertex and visit the vertices according to their heights in ascending order.

The correctness of such algortihms is usually proved using an exchange argument. Assume $M$ is the matching computed by your algortihm and $M_{\mathrm{OPT}}$ an arbitrary maximum matching. Show that you can turn $M_{\mathrm{OPT}}$ into $M$ by removing and adding edges to the matching where its size never gos smaller.