def same_fringe(tree1, tree2):
    """ Detect is the given two trees have the same fringe. A fringe is a list
    of leaves sorted from left to right.
    """
    def is_leaf(node):
        return len(node['children']) == 0

    def in_order_traversal(node):
        if node == None:
            return []

        if is_leaf(node):
            return [node['key']]

        leaves = []
        for child in node['children']:
            leaves.extend(in_order_traversal(child))

        return leaves

    leaves1 = in_order_traversal(tree1)
    leaves2 = in_order_traversal(tree2)
    return leaves1 == leaves2