Another typical week.(Talk about exercise)

In this week, I think one of the challenges on computer science for me is the exercise 3. In previous weeks' lecture, we've learned a lot of things about the traversal of tree.
There are three ways for us to traverse the trees.
1.Pre-order
2.In-order
3.Post-order

As you can see, the order or the way for these three algorithm to traverse trees are different with each others.

Pre-order

Visit the root.

Traverse the left subtree.

Traverse the right subtree.

In-order 

Traverse the left subtree.

Visit root.

Traverse the right subtree.

Post-order

Traverse the left subtree.

Traverse the right subtree.

Visit the root.

For me, I can easily traverse a tree with these algorithms. However, what make me confusing is to build a tree with given pre-order and in-order.

To solve this problem,I use the given example form the handout to draw picture and find the way to solve that.Let me explain.

[10, 6, 8, 12, 11, 15] (pre-order) 

[8, 6, 12, 10, 11, 15] (in-order)

As we already know, the order for pre-order to traverse is root-->left--->right(which shown above). Therefore, the first item(pre-order[0]) must be the root for the tree which is 10.

Then, the order for in-order to traverse is left-->root-->right. Therefore, items before 10 is the left subtree and items after 10 is the right subtree.

After that, things all become clear. 6 must be the root for the left subtree and use 6 into in-order list to split the left subtree and right subtree for the left subtree.Using this idea to keep traverse in recursive way. Finally we can get the result.

The tree will be:

[10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]

_______________________________________________________________________

Just post my code here after the due day to let everyone see my slog can have an idea about this exercise if you did not do well on it.

def make_tree(preorder, inorder):
    """
    >>> make_tree([10, 6, 8, 12, 11, 15], [8, 6, 12, 10, 11, 15])
    [10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]
    """
    
    if not preorder or not inorder:
        return None
    root = preorder[0]
    in_left = inorder[:inorder.index(root)]
    in_right = inorder[inorder.index(root) + 1:]
    pre_left = preorder[1:len(in_left) + 1]
    pre_right = preorder[len(in_left) + 1:]
    left_sub = make_tree(pre_left, in_left)
    right_sub = make_tree(pre_right, in_right)
    return [root, left_sub, right_sub]







See you in the next slog soon~~~~