Week 10 Frustrated With Markus

I have absolutely no idea why i got ZERO for week 7 SLOG and my remark form for week 3 has yet been looked at.  In the SLOG handout it said that i just have to write A paragraph or so on the assigned topics but I am pretty sure i went far beyond that. I spent my whole Friday for week7 SLOG, in which i described in detail the advantage of using recursion over iteration. I think my topic fit nicely with the assigned topic for that week which was "recursion". So even if you disagree with some of the contents in my Slog or basically don't like it , am i deserve at least 25% for following the instruction ? However, i don't think my SLOG just worth 25%. Beside from pointing out the facts, i also give plenty of demonstrations using code- that i made by myself- to back up my point. Moreover, i integrated the contents from several posts to prove my point, which don't think the professor event expect.

Another frustration is the A1 mark, while most of my friend already got their mark back, i am waiting like forever to see mine on Markus. Most people have at least 4 test reports for their A1 and i just got 1 that was post about a month ago. I don't really know what to do since i don't know how well my code run in later tests that i did not have the reports for.

But any way, let talk about an interesting problem that i encountered in the lab this week. The problem was that:

Source : Lab#9 handout

So we have to write a function named inorder which take a binary tree and return the root node of a linked list which is formed by in-order transversal of three. The problem would be much easier if we were allowed to use list or other container classes as intermediate storage site. However, we are not allowed to do so! Let walk through a very standard approach that helped me to solve such a hard problem like this:

Step 1: Assuming that we are allowed to use List as intermediate container. Let simplify the problem, what if you are asked to return the in-order transversal of the tree in form of List rather than LinkedList ? Then the solution will be very similar to this. 

def inorder2(r):
    return inorder2(r.left) + [r.item] + inorder2(r.right) if r else []

Step 2: I then asked myself that is it easy to convert a list into a LinkedList? The answer is yes.

def l_to_LL(alist):
    return LLNode(alist[0], l_to_LL(alist[1:])) if alist else None

 Step3: Although it is illegal , but we now can basically solve the initial problem by using the two function in step 1 and 2 as helper functions.

def inorder3(r):
    Tree_to_list = inorder2(r)
    list_to_LL = l_to_LL(Tree_to_list)
    return list_to_LL

 Step4: I look at my code and find a way to turn this illegal solution (since i use intermediate storage) into a legal solution. I note that list has a built-in __add__ function that can be used to concatenate one or more lists together and therefore make the task of turning a tree into a list in-order transversal so easy(Step1). It implies that if LinkedList also has an __add__ function that allows me to concatenate two LinkedList together then i can solve the problem without using any intermediate container. But we are not allowed to define another method inside the original LinkedList class, so i have to write a function 'add' that is outside of the LL class and force it to behave like the __add__ method in List. 

def add(root: LLNode, item: LLNode): # mimic the function add in list.
    old = root
    def _add(old, root, item):
        if root.link:
            return _add(old, root.link, item)
        else:
            root.link = item
            return old
    return _add(old, root, item)

def inorder(root: BTNode) -> LLNode:
    if root.left and root.right:
        return add(inorder(root.left), LLNode(root.item, inorder(root.right)))
    elif not root.left and root.right:
        return LLNode(root.item, inorder(root.right))
    elif root.left and not root.right:
        return add(inorder(root.left), LLNode(root.item))
    elif not root.left and not root.right:
        return LLNode(root.item)

The problem is solved!

The lesson i have from solving this problem is that by writing helper functions that  mimic Python list i can solve any similar problems that involve interaction between LinkedList and BinaryTree.