Recursive version of join_left and join_right
    TODO: make this iterative using a stack

def avl_join_dir_recursive(t1, t2, node, direction):
    """
    Recursive version of join_left and join_right
    TODO: make this iterative using a stack
    """
    other_side = 1 - direction
    if _DEBUG_JOIN_DIR:
        print('--JOIN DIR (dir=%r) --' % (direction,))
        ascii_tree(t1, 't1')
        ascii_tree(t2, 't2')

    if direction == 0:
        large, small = t2, t1
    elif direction == 1:
        large, small = t1, t2
    else:
        assert False

    # Follow the spine of the larger tree
    spine = large[direction]
    rest = large[other_side]
    # k_, v_ = large.key, large.value

    hsmall = height(small)
    hspine = height(spine)
    hrest = height(rest)

    if _DEBUG_JOIN_DIR:
        ascii_tree(spine, 'spine')
        ascii_tree(rest, 'rest')
        ascii_tree(small, 'small')

    if hspine <= hsmall + 1:
        t_ = avl_new_top(small, spine, node, direction)
        if _DEBUG_JOIN_DIR:
            print('JOIN DIR (BASE)')
            ascii_tree(t_, 't_')
        if height(t_) <= hrest + 1:
            if _DEBUG_JOIN_DIR:
                print('JOIN DIR (Case 1)')
            return avl_new_top(t_, rest, large, direction)
        else:
            # Double rotation, but with a new node
            if _DEBUG_JOIN_DIR:
                print('JOIN DIR (Case 2)')
            t_rotate = avl_rotate_single(t_, direction)
            if _DEBUG_JOIN_DIR:
                ascii_tree(t_rotate, 't_rotate')
                EulerTourTree(root=t_rotate)._assert_nodes('t_rotate')
            t_merge = avl_new_top(rest, t_rotate, large, other_side)
            if _DEBUG_JOIN_DIR:
                ascii_tree(t_merge, 't_merge')
                EulerTourTree(root=t_merge)._assert_nodes('t_merge')
            new_root = avl_rotate_single(t_merge, other_side)
            if _DEBUG_JOIN_DIR:
                ascii_tree(new_root, 'new_root')
                EulerTourTree(root=new_root)._assert_nodes('new_root')
            return new_root
    else:
        # Traverse down the spine in the appropriate direction
        if _DEBUG_JOIN_DIR:
            print('JOIN DIR (RECURSE)')
        if direction == 0:
            t_ = avl_join_dir_recursive(small, spine, node, direction)
        elif direction == 1:
            t_ = avl_join_dir_recursive(spine, t2, node, direction)
        else:
            raise AssertionError('invalid direction')
        t__ = avl_new_top(t_, rest, large, direction)
        if height(t_) <= hrest + 1:
            if _DEBUG_JOIN_DIR:
                print('JOIN DIR (Case 3)')
            return t__
        else:
            if _DEBUG_JOIN_DIR:
                print('JOIN DIR (Case 4)')
            return avl_rotate_single(t__, other_side)
    assert False, 'should never get here'