n AVL tree is a binary search tree that is height balanced: for each

node x$,$ the heights of the left and right subtrees of x differ by at most $1.$ To implement an

AVL tree, maintain an extra attribute h in each node such that x$.$h is the height of node x$.$

As for any other binary search tree T $,$ assume that T $.$root points to the root node.