CS 106B Final: CS 106B Final Exam 2 Winter 2013
Document Summary
Scheduled finals: simple algorithmic tracing (5 points) Diagram the binary search tree that results from adding in order the english words for the first ten counting numbers: one, two, three, four, five, six, seven, eight, nine, ten to an empty binary search tree. As in the section problem, you should use the following definition for the nodes of the bst: struct bstnode { string key; Your diagram can be very simple and need show only the value of the key in each node and a line connecting that node to its left and right subtrees. In the problem, you can omit empty subtrees entirely: recursion (15 points) As a simple example, the word cats is reducible because you can cross out first the s, then the c, and then the t, leaving the words cat, at, and a, in order.