Python 3: Binary Search Tree Algorithm COPY PASTABLE CODE: paste.ee/p/TfzwW

PROBLEM: Write a function binarySearch(self, elem) that takes in an element, elem, and returns True if element is in BST and False otherwise.

This function should be a part of the BinaryTree class.

def binary_search(self, elem):

### your code here

return

Given that the tree is balanced, algorithm can find an element in the BST in big-Theta(log n)

The tree is only balanced if:

The left and right subtrees' heights differ by at most one, AND

The left subtree is balanced, AND

The right subtree is balanced

BST algorithm steps.

Suppose I want to check if some element, toFind, is in my BST:

1. Start at the root and compare the values.

2. If they are the same, stop and return True

3. If toFind is larger than the root's value, go to the right subtree. Go to step 1.

4. If toFind is smaller then the root's value, go to the left subtree. Go to step 1.

5. Return False if reached the bottom of the tree (no children).

There are algorithms that keep binary search trees balanced when one adds or removes elements but you do not have to worry about it yet.

Write a function binarySearch(self, elem) that takes in an element, elem, and returns True if element is in BST and False otherwise.

This function should be a part of the BinaryTree class.

Note: this algorithm works only if a given binary tree is a binary SEARCH tree. Therefore your method from problem 3.2 will be handy here.

Make sure that your string is correct and matches the expected output exactly.

Expected outputs:

Balanced Binary Tree Unbalanced Binary Tree