docs: def avl_insert_dir(root, new_node, direction=1):
      """
      Inserts a single node all the way to the left (direction=1) or right (direction=1)
  
      CommandLine:
          python -m utool.experimental.euler_tour_tree_avl avl_insert_dir --show
          python -m utool.experimental.euler_tour_tree_avl avl_insert_dir
  
      Example:
          >>> # DISABLE_DOCTEST
          >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
          >>> import utool as ut
          >>> root = Node(value='A')
          >>> new_node = Node(value='B')
          >>> new_root = avl_insert_dir(root, new_node, direction=1)
          >>> new_root = avl_insert_dir(root, Node(value='Z'), direction=1)
          >>> EulerTourTree(root=new_root)._assert_nodes()
          >>> for v in ut.chr_range(5, base='C'):
          >>>     new_root = avl_insert_dir(new_root, Node(value=v), direction=1)
          >>>     self = EulerTourTree(root=new_root)
          >>>     self._assert_nodes()
          >>> new = EulerTourTree(root=new_root)
          >>> print(new)
          >>> ut.quit_if_noshow()
          >>> ut.qtensure()
          >>> new.show_nx(edge_labels=True)
          >>> ut.show_if_requested()
          >>> #ascii_tree(root)
          >>> #print(result)
      """
      if root is None:
          return new_node
      assert new_node.parent is None, str((new_node, new_node.parent))
      assert new_node.left is None
      assert new_node.right is None
      assert root.parent is None
  
      node_stack = []  # node stack
      # dir_stack = array('I')  # direction stack
      done = False
      top = 0
      # Move all the way to the right/left in tree1
      node = root
      # search for an empty link, save path
      while True:
          # Always move to the right
          # dir_stack.append(direction)
          node_stack.append(node)
          if node[direction] is None:
              break
          node = node[direction]
      extreme_node = node
  
      # Insert a new node at the bottom of the tree
      extreme_node.set_child(direction, new_node)
      new_root = root
  
      # Walk back up the search path
      # (which for joining orderless structures was always right)
      other_side = 1 - direction
      top = len(node_stack) - 1
      while (top >= 0) and not done:
          # direction = dir_stack[top]
          # other_side = 1 - direction
          top_node = node_stack[top]
          left_height = height(top_node[direction])
          right_height = height(top_node[other_side])
  
          # Terminate or rebalance as necessary
          if left_height - right_height == 0:
              done = True
          if left_height - right_height >= 2:
              a = top_node[direction][direction]
              b = top_node[direction][other_side]
  
              # Determine which rotation is required
              if height(a) >= height(b):
                  node_stack[top] = avl_rotate_single(top_node, other_side)
              else:
                  node_stack[top] = avl_rotate_double(top_node, other_side)
  
              # Fix parent
              if top != 0:
                  # d_ = dir_stack[top - 1]
                  d_ = direction
                  node_stack[top - 1].set_child(d_, node_stack[top])
              else:
                  new_root = node_stack[0]
                  new_root.parent = None
              done = True
  
          # Update balance factors
          top_node = node_stack[top]
          left_height = height(top_node[direction])
          right_height = height(top_node[other_side])
  
          top_node.balance = max(left_height, right_height) + 1
          top -= 1
      assert new_root.parent is None
      return new_root