CSC148 Lecture Week 7

I would like my summary of Object Oriented Programming concepts to be graded.

   Lab 6 this week is the first lab that I really struggled with. The function list_longest_path asked us to write a function that would find the longest path in a binary tree and return that path. The starter code came with the following docstring examples:

>>> list_longest_path(None)
[]
>>> list_longest_path(BTNode(5))
[5]
>>> list_longest_path(BTNode(5, BTNode(3, BTNode(2), None), BTNode(7, BTNode(4, BTNode(9)), BTNode(6))))
[5, 7, 4, 9]

The first two examples give us the two base cases for the algorithm. When there is no tree at all, the longest path contains nothing. When only the root is present, the longest path is obviously just the root itself.

Translated into code this would be:

 if node is None:
        return []
 elif is_leaf(node):
        return [node.data]

   The recursive case was what I really struggled with. I couldn't figure out how to keep track of all the data because we couldn't just find all possible paths, store them in a list and then look through that list, which is the type of recursion that we had been doing before. What really helped was one of my partner's ideas and actually drawing out the tree itself.

My partner, Wendy, realized that at each node we would need to look at the right node and the left node and then compare them. I then started walking through the tree starting at the root. Node 8 would ask Node 7, "What is your longest list?", then it would ask Node 1, "What is your longest list?". This would continue until a leaf was reached. The leaf would then know right off the bat that its longest path was itself. This information would then be sent back up the tree. The final piece of the puzzle was realizing that we would have to concatenate the data of the node itself to the data it was getting from it's children. This then lead to the final solution:

else:
        if not node.left == None:
            left = list_longest_path(node.left)
        else:
            left = []
         
        if not node.right == None:
            right = list_longest_path(node.right)
        else:
            right = []
         
        return [node.data] + left if len(left) > len(right) else [node.data] + right

Another slogger also has a great explanation of recursion here.