Red Rover Red Rover

Perhaps the title of the week's post is a little stupid, but that is actually the first thought that occurred to me while practicing with linked lists. Red Rover is a game children play consisting of two teams (West and East) where the goal is to try and diminish a team to only one person. The teams shout out "Red Rover, Red Rover, we call [person's name] over" and the person who was called tries to run through the other team who has linked hands together. If they succeed in breaking the link, they are allowed to return to their team otherwise they join the end of the opposing team. There's a point to this, I promise. Linked lists, like linked hands in Red Rover are very similar in that:

1. Every node contains a value (like a person) and holds a reference to another node(another person). This allows the nodes to link together similar to a list.

2. When a Linked List consists of one node (e.g. person), it only points to None (i.e. no one) or a terminator that signifies the end of the list!

3. It is easy to insert and delete nodes from the list. Instead of forcing your whole team to move in order to make space for you when you join in Red Rovers, you may link hands without changing your position (though humans are limited to how long their arms are of course and it would be easier to locate a certain person if you did change your position). Linked lists allow you to change where each node references to, making it the optimal solution if you have to insert and delete many items. Due to the fact that there is no memory reallocation since nodes do not have to be stored contiguously in memory, it's quicker when dealing with a lot of data.

This may not have been the best real world example to explain linked lists but it was just a thought.


Reading Piazza last week made me realize just the large amount of posts that were asking how e5b can be solved without a helper function and with recursion. I hope this post sheds some light on how you would go about doing that.

Let's say for some reason, we are interested in finding the height in the left subtree and the right subtree of our tree separately. We could try to approach this similar to the nested_depth example that Professor Danny showed in class a while back, but that would be... rather difficult. That approach is much easier to implement when searching for a height taking into account all paths in the tree such as:

def get_height(self: 'BTNode') -> int:

    return 1 + max([self.left.get_height() if self.left is not None else -1] +

                            [self.right.get_height() if self.right is not None else -1])

(The above example could probably improved)
N.B. The above example uses Professor Danny's hint about using -1 as a depth for an empty tree to properly calculate the height of the tree.

But since we want the heights of two different subtrees, our function should run recursively and store into two different internal variables. This is made possible with the + (list concatenation) or list.extend() method. Usually you may pass parameters in your recursive function (which makes matters much easier in my opinion) unless you are instructed against it as in our assignment.

One of the useful tips I've learned throughout the exercise is to take one variable at a time if you're having trouble. That means write the internal variable and base case for one variable, then when that works implement the other.

The recursive function can take the form (as mine did):

def get_max_depth(self: 'BTNode') -> tuple:

    leaves = []

    internals = []

    # Base case and if statements here

    leaves = (recursive call goes here, and the + or extend)

    internals = (recursive call goes here, and the + or extend)

    return leaves, internals

I'll post one of my solutions a little later so as not to give it away. Stay classy.

Now to end with a completely pointless but funny picture I found: