81 Trees 1 Answer the following questions about binary tree

8.1 Trees 1. Answer the following questions about binary tree levels. a. What does the level of a binary search tree mean in relation to the searching efficiency? b. What is the maximum number of levels that a binary search tree with 100 nodes can have? c. What is the minimum number of levels that a binary search tree with 100 nodes can have?

Solution

The level of a binary tree signifies its height but it doesnot signifies the maximum number of nodes.

The maximum number of levels that a tree can have is defined by its worst case which would be 100 levels of one node (where 100 is number of nodes)

The minimum number of levels that a tree can have is best case is 7 (here its a binarysearch tree and we calculate the best case by 2^0+2^1.... till when the sum is less than or equal to number of nodes hence (100<= 2^0+2^1+2^2+2^3+2^4+2^5+2^6) which is (100<= 1+2+4+8+16+32+64) and the count is 7.