Question

Suppose T is a binary search tree of height 4 (including the external nodes) that is
storing all the integers in the range from 1 to 15, inclusive. Suppose further that
you do a search for the number 11. Explain why it is impossible for the sequence
of numbers you encounter in this search to be (9, 12, 10, 11).

Answer 1

Answer :

1) In a BST all the nodes in the left sub-tree of the current node are smaller than the current node and all the nodes in the right sub-tree are greater than the current node. While searching for an element in the tree either the nodes visited have decreasing or increasing order of elements not both.

2) Algorithm to find smallest element in BST: Traverse from root till leaf node by recurring to left child of the current node.

smallest(T)

- Start from root node

- If currentNode->left is null:

return currentNode->data

else

smallet(currentNode->left)

Running time is equal to height of the tree, if number of elements are N then time complexity would be O(logN)

*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*end*--*-*-*-*-*-*-*-*-*-*-*-*-*-*-