CODEWITHSUNDEEP
algorithmgraphvertexcover
Haani
Haani

Reputation: 139

Minimum vertex cover of a binary tree

If you have a binary tree that has 2^n - 1 vertices, where n >= 1, what is amount of vertices needed to have a minimum vertex cover?

Upvotes: 0

Views: 856

Answers (1)

Zoomba
Zoomba

Reputation: 1806

Imagine that we have L levels (1 to L) where (n = 2^L - 1). The solution is to first pick all the nodes at level L - 1, then all nodes at L - 3, and so on. However, we stop depending on whether n is odd or even. If n is odd we stop at level 1 and if it is even we stop at level 2. This can be proved by strong induction (how ?).

Upvotes: 1

Related Questions