CSSE 230
Data Structures and Algorithm Analysis

Homework 6  -  20 points

Reading

(Towards the Reading grade) In our textbook (link at top of Moodle page), read 7.1-7.4.

To receive full credit, complete the self-quizzes as you go. (You can re-take any you don't get correct the first time; you are graded on your participation.) The reading is a zybooks "assignment" called "Reading for HW6".

To Be Turned In

This homework is short (1 problem), since we expect that you'll be spending time on the term project. Commit your work to your Git repository. You may earn a late day as usual by submitting this assignment early.

1. (20 points) Checkout the PreorderBuildTree project from your Git repository. In this problem, you'll create another Binary Tree constructor, one that constructs a Tree with Character data from two pre-order lists: a string of data and a string of children. For example, t = BinaryTree("abc", "200") would create a full tree of height 1 with root = a and two children b and c, and t = BinaryTree("cbad", "2L00") would create the minimum height-balanced tree of height 2, with an in-order traversal of "abcd".

   As a larger example, this tree was built from the strings, "ARGEDFKJHWS" and "R22200LL0L0":

   

   This format should sound familiar - see HW3 and its solution for more details. Note that this can construct any binary tree of characters, not just BSTs. I am posting two hints here, but I strongly suggest that you try to develop an algorithm first before referring to them.

Other problems for your consideration

6.31[6.17], 6.37[6.22], 7.3[7.3], 7.4[7.4], 7.23[7.19], 7.29