Binary Search Tree Exercises

1. Binary Search Tree Insertions/Searches

(a) Construct a binary search tree by inserting the following in the given sequence:

5, 10, 35, 15, 10, 70, 25, 30, 70

Show the tree after every insertion.

2. Suppose a binary search tree stores integers in the range 1 to 1000. Which of the following search sequences are not possible when searching for the value 225 in the tree?

(a) 500, 355, 150, 320, 200, 225

(b) 500, 400, 200, 300, 200, 350, 225

(c) 50, 100, 600, 400, 40, 120

(d) 50, 500, 100, 400, 200, 300

3. Suppose you are given two BSTs, the first with m entries and the second with n entries, with no duplicate keys in either. Describe an algorithm to merge the two trees into a new BST that contains all the entries of both the original BST. Your algorithm should be as fast as possible.