/dev/random

Products and trees

def product_others(L):
    """
    Return an array M where the value at each index i is the product
    of all values in L except for L[i]

    Constraint: only use multiplication operator
    """
    product = lambda x, y: x * y

    # value at index i is the product of all prev in L
    before = [
        reduce(product, L[:i], 1)
        for i in range(len(L))
    ]

    # value at index i is the product of all next in L
    after = [
        reduce(product, L[i+1:], 1)
        for i in range(len(L))
    ]

    return [x * y for (x, y) in zip(before, after)]


def reconstruct(inorder, postorder):
    """
    Reconstruct and return the root of the tree that yields the
    passed inorder and postorder traversals
    """
    assert len(inorder) == len(postorder)

    if not inorder:
        return

    # root is always last entry
    root = Node(postorder[-1])
    # find index of root in inorder
    i = inorder.index(root.data)

    # left subtree of tree rooted at root
    inorder_left = inorder[:i]
    # right subtree of tree rooted at root
    inorder_right = inorder[i+1:]

    postorder_left = postorder[:i]
    postorder_right = postorder[len(postorder_left):-1]

    root.left = reconstruct(inorder_left, postorder_left)
    root.right = reconstruct(inorder_right, postorder_right)

    return root


if __name__ == '__main__':
    L = [2, 4, 1, 3]
    assert [12, 6, 24, 8] == product_others(L)

    #
    #           1
    #          / \
    #         2   3
    #        / \ / \
    #       4  5 6  7
    #        \
    #         8
    #
    t1 = Node(1)
    t1.left = Node(2)
    t1.right = Node(3)
    t1.left.left = Node(4)
    t1.left.right = Node(5)
    t1.right.left = Node(6)
    t1.right.right = Node(7)
    t1.left.left.right = Node(8)

    A, B = [], []
    inorder(t1, A)
    postorder(t1, B)

    t2 = reconstruct(A, B)

    C, D = [], []
    inorder(t2, C)
    postorder(t2, D)

    assert A == C
    assert B == D