balanced binary search trees implementation alternatives looking back at chap and the implementation of binary search treesinserting value into tree can be written recursively inserting into an avl tree can also be implemented recursively it is also possible to implement inserting value into an avl tree iterativelyusing loop and stack this explores both alternatives additionallythe balance of an avl tree can be maintained using either the height of each node in the tree or the balance of each node in the tree implementations of avl tree nodes store either their balance or their height as values are inserted into the treethe balance or height values of affected nodes are updated to reflect the addition of the new item in the tree avlnode with stored balance class avltreeclass avlnodedef __init__(self,item,balance= ,left=none,right=none)self item item self left left self right right self balance balance def __repr__(self)return "avltree avlnode("+repr(self item)+",balance="repr(self balance)+",left="+repr(self left)",right="+repr(self right)+")whether implementing insert recursively or iterativelythe node class of chap must be extended slightly to accommodate either the balance or the height of the node consider the code fragment in sect the first implementation of avltree that we'll explore is balance storing iterative version of the algorithm notice that the avlnode implementation is buried inside the avltree class to hide it from users of the avltree class while python does not actually prevent access to the avlnode class from outside the avltree classby convention users of the avltree data structure should know to leave the internals of the tree alone avl trees are created by users of this data structurebut not avl nodes the creation of nodes is handled by the alvtree class the avlnode constructor has default values for balanceleftand right which makes it easy to construct avltrees when debugging code the __repr__ function prints the avlnode in form that can be used to construct such node calling print(repr(node)will print node so it can be provided to python to construct sample tree the repr(self leftand repr(self rightare recursive calls to the __repr__ functionso the entire tree is printed rooted at self from chap the same __iter__ function will work to traverse an avltree the iterator function will yield all the values of the tree in ascending order examples in this will refer to balance of nodes in an avl tree it turns out that storing the balance of node is sufficient to correctly implement height balanced this copy belongs to 'acha