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)

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