# Binary Search Tree Homework

## Written portion (Due Wednesday 10/14)

Neatly write your answers to these problems (**problem 1** and **problem 2**), and upload them to blackboard.

**Problem 1**: Draw the binary search tree that would result from inserting
the following sequences of numbers in the given order into an initially empty
tree.

Sequence: 8, 3, 10, 1, 6, 14, 4, 7, 13

Sequence: 15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9

**Problem 2**: Given the following binary search trees, write the order in
which the nodes would be visited using Preorder, Inorder, and Postorder
traversals:
```
      8
     / \
    3   10
   / \    \
  1   6    14
     / \   /
    4   7 13
```

```
      20
     /  \
    10   30
   / \   / \
  5  15 25 35
 /    \
2     18
```

## Coding portion (Due Wednesday 10/14).

Download [this starter BST implementation](bst.NOTpy), rename it to `bst.py`
and complete the unfinished functions as indicated below. Upload your solution to the submit site as **bst_functions**.

**Problem 3**: Many tree operations are much easier to write using recursion.
`contains(e)`, on the other hand, is just as easy to write iteratively. Write
an *iterative* (using a loop) implementation of `contains(data)`. A helper
function is not necessary. *Hint: be thinking of the iterative approach to
viewing every element of a linked list*

**Problem 4**: To the same file, add a *recursive* function which returns the
sum of all the elements in the BST. You will have to write both the
public-facing function `sum(self)` and the recursive helper function
`_sum(self, node)`.

[My solution](BSTHomeworkSolutions).