def _traversal_minlex_postorder(tree, u):
    """
    For a given input ID u, this function returns a tuple whose first value
    is the minimum leaf node ID under node u, and whose second value is
    a list containing the minlex postorder for the subtree rooted at node u.
    The first value is needed for sorting, and the second value is what
    finally gets returned.
    """
    children = tree.children(u)
    if len(children) > 0:
        children_return = [_traversal_minlex_postorder(tree, c) for c in children]
        # sorts by first value, which is the minimum leaf node ID
        children_return.sort(key=lambda x: x[0])
        minlex_postorder = []
        for _, child_minlex_postorder in children_return:
            minlex_postorder.extend(child_minlex_postorder)
        minlex_postorder.extend([u])
        return (children_return[0][0], minlex_postorder)
    else:
        return (u, [u])