AVL TREE LEFT RIGHT DOUBLE ROTATIONS, DEPTH FIRST SEARCHs, BREADTH FIRST SEARCH, RECURSIVE and ITERATIVE TRAVERSALS, HEIGHT, DEPTH, SIZE, LEAF, NODE FINDERS, ROOT to LEAF NODE PATHS

SINGLE ROTATION

DOUBLE ROTATION

Suppose the node to be rebalanced is X. 

There are 4 cases that we might have to fix (two are the mirror images of the other two):

• An insertion in the left subtree of the left child of X,
• An insertion in the right subtree of the left child of X,
• An insertion in the left subtree of the right child of X, or
• An insertion in the right subtree of the right child of X.

Balance is restored by tree rotations.

Case 1 and case 4 are symmetric and requires the same operation for balance. 

Cases 1,4 are handled by single rotation.

Case 2 and case 3 are symmetric and requires the same operation for balance.

Cases 2,3 are handled by double rotation