docs: 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'