# Binary Trees

• May 31st 2009, 04:32 PM
kurac
Binary Trees
Let t be a binary tree with 2148 vertices.

1)Is it possible that the height of T is less than 8? No, because -1 + 2 ^(7+1) = 255.

If t is a full then:

2) the number of leaves? 2047
3) the number of internal vertices? 1124
4) the height of t? 11.

Can someone check these please. Someone on the forum gave me a formula but im not sure if i used it correctly. Thanks!
• Jun 6th 2009, 01:05 PM
pinkandbrown
Quote:

Originally Posted by kurac
Let t be a binary tree with 2148 vertices.

Are you sure the number of vertices (nodes) is 2148 and it is a full binary tree? isn't a full binary tree a tree where each vertex has two children except the leaf nodes?

if so I don't think a full binary tree can have an even number of vertices (nodes), because the number of nodes in each level except the root is even and that means the full tree should have an odd number of vertices (even + odd = odd). The number of vertices a specific level is given by the equation:

number of vertices in level L = 2^L

so in level 0 (root) we have 2^0 = 1 vertix
in level 1 ...... we have 2^1 = 2 vertices
in level 2 ...... we have 2^2 = 4 vertices

anyway ...

Quote:

Originally Posted by kurac
1)Is it possible that the height of T is less than 8? No, because -1 + 2 ^(7+1) = 255.

Your answer is true. because the height of this tree should equal to the Integer[log2(2148)] = Integer[11.0687783] = 11

Quote:

Originally Posted by kurac
If t is a full then:

2) the number of leaves? 2047
3) the number of internal vertices? 1124
4) the height of t? 11.

Can someone check these please. Someone on the forum gave me a formula but im not sure if i used it correctly. Thanks!

I think there is something wrong here, because the number of nodes should be equal to the summation of the internal vertices and the leaves.

number of nodes = number of leaves + number of internal vertices
2148 = 2047 + 1124
2148 = 3171 which means there is something wrong. Thats why I doubt that there is a full binary tree which contains 2148 vertices.

Anyway, as far as I know,
the number of internal nodes = number of all nodes in the tree / 2 + 1
the number of leaves = number of nodes in the tree / 2

lets consider a full binary tree of 7 vertices (nodes), so n = 7:
........*
.....*.....*
...*.*...*.*

number of internal vertices = n/2 = 7/2 = 3
number of leaves vertices = n/2 +1 = 7/2+1 = 4
height of tree = Integer[log2(n)] = Integer[log2(7)] = Integer[2.8] = 2

I hope that helped