Question

What does the level of a binary search tree mean in relation to its searching efficiency? In your response discuss what the maximum number of levels to implement a search tree with 100 nodes and what is the minimum number of levels for 100 nodes. In your response to other students discuss if you agree with the other student’s number of levels, how the number of levels was determined and the Big-O efficiency of the maximum and a minimum number of levels.

Answer 1

Question: What does the level of a binary search tree mean in relation to its searching efficiency?
Answer: Search efficiency decreases with increasing levels.
Description:
Binary Search Tree (BST) is a binary tree based Data Structure which has the dollowing properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree

Searching in a binary Tree is done utilizing the fact that all keys those are less than the root are in the left sub tree and all the keys which are greater than the root's ksy are on the right.
In this way, we visit a single node in each level.
So worst case Time complexity of a BST search operation is O(levels).

In your response discuss what the maximum number of levels to implement a search tree with 100 nodes and what is the minimum number of levels for 100 nodes.

Now number of levels depends on how we structure the tree and the order of arrival of keys.
As asked in the question, suppose we have to implement a search tree with 100 nodes.
For a Binary Tree, maximum number of levels possible for a tree with 100 nodes is 100.
Now, let us see how would this occur in a Binary Search Tree.
And the nodes arrive in increasing order, i.e. a value/key arriving later to be inserted will always be less than a value/key arriving earlier to be inserted.
In such a case, we will have 100 levels. As the tree will be a right skewed tree.
So the maximum number of levels is 100.

Minumum number of levels will be when the tree is a fully balanced binary tree.
Minimum number of levels will be log₂100.

Suppose we have tree with n nodes, than maximum number of levels in a BST is n, and minimum number of levels is log₂n.
Hence, Big-O efficiency of searching with maximum number of levels in the Binary Search Tree is O(n).
And Big-O efficiency of searching with minimum number of levels in the Binary Search Tree is O(log₂n).