To add a new element X to a binary search tree:

A) If the tree is empty, make X the root of a new tree; otherwise, compare X to the root, if X is less, put it in the left subtree, if it is greater, put it in the right subtree
B) First add X in the position of the root. If X is a leaf, or is less than its children, stop. Otherwise, repeatedly swap X with the smaller of its two children until X becomes a leaf or becomes less than its children.
C) Add X as a leaf, taking care to preserve the search tree structure. If X is now the root, or is greater than its parent, stop. Otherwise, repeatedly swap X with its parent until X becomes the root or becomes greater than its parent.
D) Insert X using the same algorithm for insertion in an AVL tree. If the tree remains balanced, stop. Otherwise, execute a rebalancing operation.

A) If the tree is empty, make X the root of a new tree; otherwise, compare X to the root, if X is less, put it in the left subtree, if it is greater, put it in the right subtree