Develop a simple encryption scheme using a binary search tree. To encode a sentence, insert each letter into a binary tree using the ASCII value as a comparative measure.

To encode the sentencemeet me, start by inserting the letters "m", followed by "e" and followed by "t" into the binary tree. In the first insertion, the binary tree is empty, so "m" becomes the root node of the tree. The "e" is inserted next. Since "e" is less than "m", it becomes the left child of "m" node. The second "e" is not inserted as there is an "e" in the tree already. The "t" becomes the right child of the "m" node. The next character is the space character and is considered less than any letter and becomes the left most leaf.

To encode, use the following convention: assign the root node of the tree a "*" character. Every other character in the tree, assign a character string based on how many "lefts" and how many "rights" are involved in the tree traversal. For "left" traversals, use a "<", for "right" traversals use a ">". In the above example, "e" will be represented as "<" and "t" will become ">". The space character will become "<<". To complete the code, every character must be separated by a marker called the delimiter. Use "!" (the exclamation mark) as a delimiter for the code.

Using these conventions, the string"meet me"when encrypted becomes"*!!<.

For this assignment we are only going to encrypt lower case letters "a" through "z" and the space character. When the input string is given for encryption, convert it to lower case. Only encrypt the lower case letters and spaces. Ignore all digits, punctuation marks, and special characters. Basically, you will drop the the digits, punctuation marks and special characters.

For the encryption to work, a key has to be given. This key is used to create the binary search tree. The encryption key for this assignment is"the quick brown fox jumps over the lazy dog".

Modify the Binary Search Tree given code. Here is a suggested outline of that:

import sys class Tree (object): # the init() function creates the binary search tree with the # encryption string. If the encryption string contains any # character other than the characters 'a' through 'z' or the # space character drop that character. def __init__ (self, encrypt_str): # the insert() function adds a node containing a character in # the binary search tree. If the character already exists, it # does not add that character. There are no duplicate characters # in the binary search tree. def insert (self, ch): # the search() function will search for a character in the binary # search tree and return a string containing a series of lefts # (<) and rights (>) needed to reach that character. It will # return a blank string if the character does not exist in the tree. # It will return * if the character is the root of the tree. def search (self, ch):