Week 6: Binary Tree

This week we learnt about binary tree, which has three ways to be represented.

The first one is preorder.

def preorder(tl: 'TreeList') -> list:
    """
    Return list of values in tl in preorder

    >>> preorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [5, 4, 3, 2, 1]
    """
    return [] if tl is None else ([tl[0]] + preorder(tl[1]) + preorder(tl[2]))

Second one is post order,like below.

def postorder(tl: 'TreeList') -> list:
    """
    Return list of values in tl in postorder

    >>> postorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [4, 2, 1, 3, 5]
    """
    return [] if tl is None else postorder(tl[1]) + postorder(tl[2]) + [tl[0]]

The last one is inorder.

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 [] if tl is None else inorder(tl[1]) + [tl[0]] + inorder(tl[2])

Every binary tree can be represented in such ways, and if we want a certain binary tree, we only need to know the preorder list and in order list of that binary tree.