Suppose you begin with an empty binary search tree, and want to add all the positive integers from 1 through 31 to the tree. If the first number you add to the tree is 16, what is the smallest possible height of the tree?

4

Explanation:

Trees are data structures fundamental in computer science, widely used in these fields because they are well adapted to the natural representation of homogeneous organized information, and great convenience and speed of manipulation.

A tree is a data structure (often dynamic) representing a set of hierarchically organized (non-linear) values. Each value is stored in a node. The nodes are joined to each other by the edges which represent parent/child relationships.

We can define a binary search tree as a root binary tree with the presence of its internal nodes which usually stores a key that is higher than all the keys remaining in the sub-tree of the left node and lower than those in the right sub-tree.

From the given information; if we want to add all +ve integers from 1 → 31 to the tree and we intend that the first number that to be added should be 16, then the smallest possible height of the tree will be 4.

The right sub-tree computation for the tree diagram can be seen in the image below.