Question

number of pendant vertices in a binary tree with n vertices n+1/2?​

Answer 1

Answer:

the number of pendant vertices is (n+1)/2. In a full binary tree, only one vertex, namely, the root is of even degree (namely 2) and each of the other (n-1) vertices is of odd degree (namely 1 or 3.)

Step-by-step explanation:

Answer 2

Given:

A binary tree with n vertices

To prove:

The number of pendant vertices = (n+1) / 2

Solution:

In a full binary tree, only the root is of even degree and each of the other (n-1) vertices is of odd degree.

Since the number of vertices of odd degree in an undirected graph is given even, (n-1) is even.

⇒ n is odd

Now let p be the number of pendant vertices of the full binary tree.

So, the number of vertices of degree 3 = n - p - 1

⇒The sum of the degrees of all the vertices of the tree =1×2+p×(n−p−1)×3

=3n−2p−1

Since each edge contributes 2 degrees,

Number of edges of the tree = 1/2 X (3n−2p−1)  

But we know that the number of edges of a tree with n vertices=n-1

Equating the two expressions,

⇒ 1/2(3n−2p−1) = n−1

or 3n−2p−1 = 2n−2

or 2p = n+1

⇒ p=n+1 / 2

∴ Hence, proved