In order to find minimum size of X capable of
storing any kind of binary tree, the worst case
size of the tree has to be taken.
In the worst case size of the tree has to be taken.
In the worst case only a single node will contain
the data at each level of the tree.
For example, for 4 data items, the worst case
binary tree will be as follows
Generalizing the concept, for n vertices, the levels
of tree that are required will be n.
Memory required at each level (starting from root)
will be 20, 21, 22, .... 2n-1
∴ Minimum size = 20 + 21 + 22, .... 2n-1
= 20(2n-1)/(2-1) = 2n-1
Generalizing the concept, for n vertices, the levels
of tree that are required will be n.
Memory required at each level (starting from root)
will be 20, 21, 22, .... 2n-1
∴ Minimum size = 20 + 21 + 22, .... 2n-1
= 20(2n-1)/(2-1) = 2n-1
cd is maximum weight edge and it must present
in minimum spanning tree
Total sum = 1 + 2 + 2 + 2 + 3 + 4 + 4 + 5 + 8 = 31