join two trees without any intermediate key

    Returns:
        Node: new_root

    O(log(n) + log(m)) = O(r(t1) + r(t2))

    For AVL-Trees the rank r(t1) = height(t1) - 1

def avl_join2(t1, t2):
    """
    join two trees without any intermediate key

    Returns:
        Node: new_root

    O(log(n) + log(m)) = O(r(t1) + r(t2))

    For AVL-Trees the rank r(t1) = height(t1) - 1
    """
    if t1 is None and t2 is None:
        new_root = None
    elif t2 is None:
        new_root = t1
    elif t1 is None:
        new_root = t2
    else:
        new_left, last_node = avl_split_last(t1)

        debug = 0

        if debug:
            EulerTourTree(root=new_left)._assert_nodes('new_left')
            EulerTourTree(root=last_node)._assert_nodes('last_node')
            EulerTourTree(root=t2)._assert_nodes('t2')

            print('new_left')
            EulerTourTree(root=new_left).print_tree()

            print('last_node')
            EulerTourTree(root=last_node).print_tree()

            print('t2')
            EulerTourTree(root=t2).print_tree()

        new_root = avl_join(new_left, t2, last_node)

        if debug:
            print('new_root')
            EulerTourTree(root=new_root).print_tree()
            EulerTourTree(root=last_node)._assert_nodes('new_root')
    return new_root