Binary Search Tree

The search tree property is as follows: Every thing to the left of the node is less than it and everything to the right is greater. There are many possible trees for the same set of keys. The height can range anywhere from log₂n to n. Therefore, the worst possible running time for searching a key or inserting a key is O(height).

Getting Minimum
You can just traverse left down the tree since everything left is less than what you are at now.

Getting Maximum
This is the same concept as minimum but you move to the right.

Finding Predecessor
Easy Case - If k's left subtree is not empty, just return the max key in its left subtree.
Harder Case - Go up parent pointers until you reach one that is less than you.

In-Order Traversal
Let R be the root node of the search tree, with substrees T_l and T_r. Recurse on T_l. Next print out R's key. Lastly, recurse on T_r.

Deletion
First we need to search for the node. Then we have three cases:
(1) k has no children (easy) - Then we can just delete the node without any consequences
(2) k has one child (medium) - The unique child assumes the place of the parent node
(3) k has two children (hard) - We can sneakily compute the predecessor. That is, traverse k's non-null left child and then follow right child pointers until no longer possible to get l. Swap k and l. We know k now must have no right child since we followed them all. Then we know how to delete it if it has 0 or 1 child.

Note:
We can store the size of the tree at each node. If x has children y, x, then size(x) = size(y) + size(z) + 1. We also have to maintain this variable each time we do insertion or deletion as well.

Select
The goal is to select the ith order statistic. Start with root x with children y and z.
(1) If i==size(y)+1, then return x's key.
(2) If i<=size(y), then recurse on y.
(3) if i-1 > size(y), then recursively compute (i-size(y)-1)th order statistic on search tree rooted at z.
The running time for this is still O(height).