Week 5

       In this week class, we learn about treelist with preoder, postorder and inorder. We learn about how to create a binary tree. The tree just like a combination of nodes, has leaf: node with no children, internal node: node with one or more children, subtree: tree formed by any tree node together with its descendants and the edges leading to them. And there is a unique path from root to each node. And again, we learn how to do it by using recursion.
def preorder(tl: 'TreeLIst') -> list:
    if tl == None:
        return []
    else:
        return [tl[0]] + preorder(tl[1]) + preorder(tl[2])
 
#print(preorder([5, [4, [2, None, [3, None, None]],[6, [7, None, None], None]], [3, [2, None, None], [1, None, None]]]))
#print(preorder([10, [6, [8, None, None], None], [12, [11, None, None], [15, None, None]]]))

'''
                       5
                 4           3
              2    6       2   1
            N   3        N  N N N
               N N
                       5
                 4           3
               2   N       9   1
              8 3
               N  6
                 7  N

postorder [6 3 2 4 2 1 3 5]
inorder [2 3 6 4 5 2 3 1]

[10, 6, 8, 12, 11, 15]
                         10
                      6     11
                    8  12     15
[8, 6, 12, 10, 11, 15]
                         
'''
'''
def inorder(tl: 'TreeList') -> list:

    return ((inorder(tl[1]) if tl[1] else []) + [tl[0]] +
            (inorder(tl[2]) if tl[2] else []))
'''
def inorder(tl: 'TreeList') -> list:
    """
    Return a list of values of tl inorder

    >>> inorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [4, 5, 2, 3, 1]
    """

    return ((inorder(tl[1]) if tl[1] else []) +
            [tl[0]] +
            (inorder(tl[2]) if tl[2] else []))


print(inorder([5, [4, [2, [8, None, None], [3, None, [6, [7, None, None], None]]], None], [3, [9, None, None],
                                                          [1, None, None]]]))


def postorder(tl:list):
    return ((postorder(tl[1]) if tl[1] else []) + (postorder(tl[2]) if tl[2] else []) + [tl[0]])

'''
print(postorder([5, [4, [2, None, [3, None, [6, None, None]]], None], [3, [2, None, None],
                                                          [1, None, None]]]))

print(inorder([10, [6, [8, None, None], None], [12, [11, None, None], [15, None, None]]]))
print(preorder([10, [8, [6, None, None], [12, None, None]], [11, None, [15, None, None]]]))
print(inorder([10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]))
print(preorder([10, [6, None, None], [8, None, [12, [11, None, None], [15, None, None]]]]))
print(inorder([10, [6, None, None], [8, None, [12, [11, None, None], [15, None, None]]]]))
print(preorder([10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]]))
print(inorder([10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]]))
    #10,6,8,12,11,15
    '''