avl treesbut perhaps bit more difficult to maintain than maintaining the height of each node in the tree later in the modifications to these algorithms are discussed that maintain the height of each node whether storing height or balance in avl treesthe complexity of the tree operations is not affected avl tree iterative insert as described in the last sectionthere are two variants to the insert algorithm for height balanced avl trees insert can be performed iteratively or recursively the balance can also be stored explicitly or it can be computed from the height of each subtree this section describes how to maintain the balance explicitly without maintaining the height of each node iteratively inserting new value in height balanced avl tree requires keeping track of the path to the newly inserted value to maintain that patha stack is used we'll call this stack the path stack in the algorithm to insert new nodewe follow the unique search path from the root to the new node' locationpushing each node on the path stack as we proceedjust as if we were adding it to binary search tree as we proceed along the path to the new node' destinationwe push all the nodes we encounter onto the path stack we insert the new item where it should be according to the binary search tree property thenthe algorithm proceeds popping values from the path stack and adjusting their balances until node is found that has balance not equal to zero before being adjusted this nodewhich is the closest ancestor with non-zero balanceis called the pivot based on the pivot and the location of the new value there are three mutually exclusive cases to consider which are described below after making the adjustments in case below there may be new root node for the subtree rooted at the pivot if this is the casethe parent of the pivot is the next node on the path stack and can be linked to the new subtree if the path stack is empty after popping the pivotthen the root of the tree was the pivot in this casethe root node of the avl tree can be made to point to the new root node in the tree as mentioned aboveone of three cases will arise when inserting new value into the tree case no pivot there is no pivot node in other words the balance of each node along the path was in this case just adjust the balance of each node on the search path based on the relative value of the new key with respect to the key of each node you can use the path stack to examine the path to the new node this case is depicted in fig where is to be added to the avl tree in each node the value is on the left and the balance is given on the right each of the nodes containing and are pushed onto the path stack the balance of the new node containing is set to the new balance of the node containing is - the node containing has new balance of the balance of the root node after the insert is because is inserted to the right of it and therefore its balance increases by one the new value is inserted to the left of the node containing so its balance decreases by one figure depicts the tree after inserting the new value this copy belongs to 'acha