Can someone please check my answers.
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!
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?Originally Posted by kurac
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 ...
Your answer is true. because the height of this tree should equal to the Integer[log2(2148)] = Integer[11.0687783] = 11
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
  |
LinkBack URL
About LinkBacks