Week 8

The coming week assignment 2 is due, my partner and I have been working on it the whole week. Assignment 2 is quite hard especially minimax. This week we studied about binary trees. A binary tree is a tree with branching factor 2. The children are called the left and right child. We talked about tree traversal, there are three standard orders in which to traverse; in-order traversal, pre-order traversal and post-order traversal. We also talked about binary search trees. This is an example of a BST:

In lecture we wrote some code for binary tree node. We implemented a function which returns whether the binary tree contains the specified value. We wrote two different versions on this function.

def bst_contains_v1(node, v):
    ''' (BTNode, v) -> bool
    
    Return whether the binary tree rooted at node contains v.
    
    Assumption: node is the root of a binary search tree.

    >>> b = BTNode(5, BTNode(3, BTNode(1), BTNode(4)), BTNode(7))
    >>> contains(b, 17)
    False
    >>> contains(b, 5)
    True
    >>> contains(b, 3)
    True
    >>> contains(b, 4)
    True
    '''
    if v == None:
        return False
    elif v == node.data:
        return True
    elif v < node.data:
        return contains(node.left, v)
    else:
        return contains(node.right, v)

I found this version to be easier than the other one.