Log2? Really?

OK, let's find out whether a binary tree's depth of search is typically log2(N).

  • Create a new method for your BinTree class called has_depth(self,V) which will search the tree for the value V and return the depth (level) of the tree where it was found (root = 1), or, if not found, then the level of leaf where it gave up. In other words, it counts the number of nodes examined in the search.

Example: if you have a tiny 3-element binary tree with root = 5, left child = 7 and right child = 3,
then has_depth(5) -> 1, has_depth(7) -> 2 and has_depth(20) -> 2

  • Create a function called Process(infilename, outfilename). This will read the named input file, which will consist of two lines of comma-separated integers. Create a binary tree and put the first line's integers into it. Remember to convert the strings to integers first -- if you don't, you'll get different results than I did. Then, use the binary tree's has_depth() method to search for each of the integers in the second line. For each of the searched integers, remember the depth of the search returned by has_depth(). Finally, write to the output file a single, comma-separated line with all the depths of the searches you found (in the same order as in the second input line).

Example: if the input file contains the following 2 lines:

5,2,4,2,10,8,1,16,5,1
4,8,7,5,16,1,9,2,10
Process() should yield the following line that it will write to the output file (verify this): 
3,3,3,1,3,3,3,2,2
If, instead, you get the following output, then the error is that you have not converted the string versions of the input numbers to integers, but left tham as strings: 
3,2,2,1,4,4,2,2,3

  • Along the way, let's test the log2ishness of this algorithm. Find the average of the output numbers and compare it to the log2(number of values in the tree). Print these two numbers and put them into the Comments-to-Teacher.

  • Since, ultimately, we want to drive the whole process from the command-line, after testing in an IDE (preferably Jupyter), you'll need a .py file that can be called from the command-line like this:

$ python3 BinTree2.py infred.csv outfred.csv

Then you can drive the whole process with a main function that looks like this:

import sys

def main():
    Process(sys.argv[1],sys.argv[2])