COS 226 Exercises on Binary Search Trees

NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Binary Search Trees

Reference: Section 3.2 in Algorithms 4/e

1. Draw the sequence of BSTs (include the symbol table keys but suppress the values) that result when you insert the following keys in that order into an initially empty tree, as in the figure on p. 402. Draw all of the null links.

P R I N C E T O G S

2. Draw the perfectly-balanced BST (of height 3) containing the keys A B C D E F G H I J K L M N O. Then, draw the BST that results when you delete I, then H using the Hibbard deletion algorithm described on page 410.