Thread: [SOLVED] Graph Theory Question - Vertices

Hello guys,

I have a question concerning the relationship between vertices in a full binary tree and the internal vertices in a full binary tree. I'm assuming there is a formule for this problem, but I have been unable to locate it.

Thanks for the help, I really need to solve this question:

If a full binary tree has 231 vertices, then it has ____ internal vertices.


Thanks guys and gals!

Originally Posted by MathHelp12345

Hello guys,

I have a question concerning the relationship between vertices in a full binary tree and the internal vertices in a full binary tree. I'm assuming there is a formule for this problem, but I have been unable to locate it.

Thanks for the help, I really need to solve this question:

If a full binary tree has 231 vertices, then it has ____ internal vertices.


Thanks guys and gals!

The definition of full binary tree is "a tree in which every node other than the leaves has two children" (Wikipedia). If you draw them on paper, you will notice that you start out with just one vertex, which we can call a leaf, then after that each leaf creates two new leaves while becoming itself an internal vertex. So, each time you add two branches to a leaf, you destroy one leaf and create two more. The overall effect is that the number of leaves is always one greater than the number of internal vertices. So, we could write

n + (n+1) = 231

Originally Posted by undefined

The definition of full binary tree is "a tree in which every node other than the leaves has two children" (Wikipedia). If you draw them on paper, you will notice that you start out with just one vertex, which we can call a leaf, then after that each leaf creates two new leaves while becoming itself an internal vertex. So, each time you add two branches to a leaf, you destroy one leaf and create two more. The overall effect is that the number of leaves is always one greater than the number of internal vertices. So, we could write

n + (n+1) = 231

Thanks for your help again!

If I'm understanding this correctly the work and answer is as followed:

n vertices has i = (n-1)/m

i = (231-1)/2 => 115.

Originally Posted by MathHelp12345

Thanks for your help again!

If I'm understanding this correctly the work and answer is as followed:

n vertices has i = (n-1)/m

i = (231-1)/2 => 115.

I think the "m" is supposed to be a 2? Anyway, that's what I get too.

Originally Posted by undefined

I think the "m" is supposed to be a 2? Anyway, that's what I get too.

Yep! The 'm' is the m-ary tree, which in this case is 2.

Thanks for your help!

Originally Posted by MathHelp12345

Yep! The 'm' is the m-ary tree, which in this case is 2.

Thanks for your help!

Oh, good call! Didn't think of that.