2. Binary search tree: insertion, deletion, successor, traversal, balance.

(1) Insertion: always insert to leaf; need to find the parent of the insertion position, O(h).

(2) Deletion: assume delete z.

z has not child: just delete.

z has only one child: replace z by its child.

z has both left/right child: find leftmost node in z's right subtree y. If y==z.right, replace z by y. Otherwise replace y by y's right child, and then replace z by y.

http://geeksquiz.com/binary-search-tree-set-2-delete/

(3) Successor:

http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/

(4) Preorder, in-order, and post-order traversal using iterative methods.