of rotation. Assuming this is a binary search tree, as stated above, the elements must be interpreted as variables that can be compared to each other. The alphabetic characters to the left are used as placeholders for these variables. In the animation to the right, capital alphabetic characters are used as variable placeholders while lowercase Greek letters are placeholders for an entire set of variables. The circles represent individual nodes and the triangles represent subtrees. Each subtree could be empty, consist of a single node, or consist of any number of nodes. Detailed illustration When a subtree is rotated, the subtree side upon which it is rotated increases its height by one node while the other subtree decreases its height. This makes tree rotations useful for rebalancing a tree. Consider the terminology of Root for the parent node of the subtrees to rotate, Pivot for the node which will become the new parent node, RS for the side of rotation and OS for the opposite side of rotation. For the root Q in the diagram above, RS is C and OS is P. Using these terms, the pseudo code for the rotation is: Pivot = Root.OS Root.OS = Pivot.RS Pivot.RS = Root Root = Pivot This is a constant time operation. The programmer must also make sure that the root's parent points to the pivot after the rotation. Also, the programmer should note that this operation may result in a new root for the entire tree and take care to update pointers accordingly. Inorder invariance The tree rotation renders the inorder traversal of the binary tree invariant. This implies the order of the elements is not affected when a rotation is performed in any part of the tree. Here are the inorder traversals of the trees shown above: Left tree: ((A, P, B), Q, C) Right tree: (A, P, (B, Q, C)) Computing one from the other is very simple. The following is example Python code that performs that computation: def right_rotation(treenode): """Rotate the specified tree to the right.""" left, Q, C = treenode A, P, B = left return (A, P, (B, Q, C)) Another way of looking at it is: Right rotation of node Q: Let P be Q's left child. Set Q's left child to be P's right child. [Set P's right-child's parent to Q] Set P's right child to be Q. [Set Q's parent to P]