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, 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).