How many edges does a full binary tree with 1000 internal vertices have?

Question

Following my textbooks definition of a full binary tree, which is: If T is a full binary tree with i internal vertices, then T's total vertices = 2i + 1. So with 1000 internal vertices, there would be 2001 total vertices.

I then used this formula to calculate the number of edges. E = (total vertices)-1. The answer would then be 2000 edges, Am I right?

You ought to mention the other formula that you used (relating number of edges to number of vertices in a tree). — Sammy Black, May 01 '14 at 21:15

score 1 · Accepted Answer · answered May 01 '14 at 21:55

Yes. $$ |E| = |V| - 1 = \left( 2|V_{int}| + 1 \right) - 1 = 2 |V_{int}|, $$ and $$ 2 \cdot 1000 = 2000. $$

However, it's easy to see the answer directly. In a full, binary tree, each internal vertex has exactly two edges emanating from it. End of story.

How many edges does a full binary tree with 1000 internal vertices have?

1 Answers1