############################################################
# AI HINTS SURVEY
############################################################


# Please take two minutes to fill out the survey if you haven't already.
# https://forms.gle/4ZQpMBMPY2ZGxSj8A


############################################################
# QUESTION 1
############################################################


# In this problem, you will implement three classes according to the
# specification below: one Container class, one Stack class (a subclass of
# Container), and one Queue class (a subclass of Container).

# Our Container class will initialize an empty list. The two methods we will
# have are to calculate the size of the list and to add an element. The second
# method will be inherited by the two subclasses. We now want to create two
# subclasses of this generic Container class so that we can add more
# functionality -- the ability to remove elements from the list. A Stack and a
# Queue will add elements to the list in the same way, but will behave
# differently when removing an element.

# A stack is a last in, first out data structure. When implementing your Stack
# class, you will have to think about which end of your list contains the
# element that has been in the list the shortest amount of time. This is the
# element you will want to remove and return.

# A queue is a first in, first out data structure. When implementing your Queue
# class, you will have to think about which end of your list contains the
# element that has been in the list the longest. This is the element you will
# want to remove and return.


class Container(object):
    """
    A container object is a list and can store elements of any type
    """
    def __init__(self):
        """
        Initializes an empty list
        """
        self.myList = []

    def size(self):
        """
        Returns the length of the container list
        """
        # Your code here

    def add(self, elem):
        """
        Adds the elem to one end of the container list, keeping the end
        you add to consistent. Does not return anything
        """
        # Your code here

class Stack(Container):
    """
    A subclass of Container. Has an additional method to remove elements.
    """
    def remove(self):
        """
        The newest element in the container list is removed
        Returns the element removed or None if the queue contains no elements
        """
        # Your code here

class Queue(Container):
    """
    A subclass of Container. Has an additional method to remove elements.
    """
    def remove(self):
        """
        The oldest element in the container list is removed
        Returns the element removed or None if the stack contains no elements
        """
        # Your code here


############################################################
# QUESTION 2
############################################################


# In class, we've used dictionaries to represent the edge connections in graph
# structures. Sometimes, graphs are so large that it's impractical to store all
# the edges in one object. Instead, we might store edge information directly
# with the nodes they connect. Classes offer us a way to express this, where we
# can operate on explicit Node objects instead of Graphs.

# For this exercise, we'll stick with directed binary tree graphs, which are
# trees where each node can have at most two children. Recall that a node with
# no children is called a leaf. Below is an implementation of the Node class.


class Node:

    def __init__(self, value, left_child=None, right_child=None):
        if left_child is None:
            self.left = None
        elif isinstance(left_child, Node):
            self.left = left_child
        else:
            raise TypeError("Left child not an instance of Node")

        if right_child is None:
            self.right = None
        elif isinstance(right_child, Node):
            self.right = right_child
        else:
            raise TypeError("Right child not an instance of Node")

        self.value = value

    def get_left_child(self):
        return self.left

    def get_right_child(self):
        return self.right

    def get_value(self):
        return self.value

    def is_leaf(self):
        return self.left is None and self.right is None


# As we've seen with trees, any Node in a tree is the root of a subtree.
# Implement a get_tree_size(node) function that determines how many nodes are in
# a given node's subtree.


def get_tree_size(node):
    """
    Given a Node object (node) in a directed binary tree, return the
    number of Nodes in the tree rooted at node.
    """


# For example, given the following code:

root1 = Node(8,
             Node(2, Node(1), Node(5)),
             Node(10))
root2 = Node(7,
             Node(2,
                  Node(1),
                  Node(5, Node(4), Node(6))),
             Node(9, Node(8), Node(10)))

# then get_tree_size(root1) should evaluate to 5 and get_tree_size(root2) should
# evaluate to 9.

# Hint: You will need to traverse the subtree using either DFS or BFS.

# Write your function below: