CMU 15-110 Fall 2018: Principles of Computing
Homework 10 (Due Sunday 18-Nov at 8pm)

• Team vs Solo:
  This hw does not have a collaborative team portion. It only has a solo portion. Please see the syllabus for details.


• Starter code:
  To start the solo hw, download this file: hw10.py. Then, edit that file you downloaded!

• This part of the hw is solo and not collaborative. See the syllabus for details.
• Note: unless otherwise stated, functions must be non-destructive.

1. preOrderString(tree, position, s) [30 points]
   Write the recursive function preOrderString(tree, position, s) that takes a binary tree represented as a list of single characters, with the root in index 1, which is the starting index, and an initially empty string, and returns a string containing the sequence of characters that are produced when the tree is traversed in a preOrder traversal. This will be very similar to the inOrder traversal covered in lecture and in the notes. Recall that the left child of a node at index i will be at index i * 2, and the right child, if it exists, will be at index i * 2 + 1.


2. countNodes(tree, position) [30 points]
   Write the recursive function countNodes(tree, position) that takes a binary tree represented as a list of single characters, with the root in index 1, which is the starting index, and returns a count of all the nodes (vertices) in the tree. countNodes([ ], 1) should return 0 as there are no nodes in that tree. Recall that the left child of a node at index i will be at index i * 2, and the right child, if it exists, will be at index i * 2 + 1.


3. inBST(tree, position, target) [40 points]
   Write the recursive function inBST(tree, position, target) that takes a binary search tree represented as a list of single characters, with the root in index 1, which is the starting index, and a target value to search for, and returns True if that value is in the tree and False otherwise. Recall that the left child of a node at index i will be at index i * 2, and the right child, if it exists, will be at index i * 2 + 1.


4. bonus/optional: countLeaves(tree, position) [2.5 points]
   Write the recursive function countLeaves(tree, position) that takes a binary tree represented as a list of single characters, with the root in index 1, which is the starting index, and returns a count of all the leaves (nodes with no children) in the tree. countLeaves([ ], 1) should return 0 as there are no nodes in that tree. countLeaves([None, 'D']) should return 1. Recall that the left child of a node at index i will be at index i * 2, and the right child, if it exists, will be at index i * 2 + 1.