Ordered search tree of nodes and edges connecting nodes

- Only one path between any two nodes
- In binary trees, all nodes have
0 ,1 , or2 children - All keys in left subtree of node X are less than X's key; all keys in right subtree of X are greater than X's key
Search in binary tree: compare search key to root's key, if less/greater than root, search recursively in left/right tree respectively; else return current node

- Runtime of search on balanced/bushy binary tree:
logN (since height of tree islogN ) - Bushy trees are
*very*fast

static BST find(BST T, Key sk) {if (T == null)return null;if (sk.keyequals(T.label()))return T;else if (sk ≺ T.label())return find(T.left, sk);elsereturn find(T.right, sk);}- Runtime of search on balanced/bushy binary tree:
Inserting new key into tree:

- Search for key; if found do nothing
- If not found after search, create new node at current location after the search

static BST insert(BST T, Key ik) {if (T == null)return new BST(ik);if (ik ≺ T.label())T.left = insert(T.left, ik);else if (ik ≻ T.label())T.right = insert(T.right, ik);return T;}Deleting a key from a BST:

- Three cases: key has no children, one child, or two children
- Case 1 - no children:
- simply sever link to parent, the now isolated key gets reclaimed by memory

- Case 2 - one child:
- Make key node's parent point to key node's child (can do this because of BST property - just like the key node is smaller/larger than parent, the key node's lone child is also smaller/larger than the key node's parent)
- If deleting root node and root has only one child (no parent), then child simply becomes new root

Case 3 - two children:

- If deleting a node k, use Hibbard deletion to select a new node to go at position k
- Replace with the rightmost(largest)/leftmost(smallest) element of the left/right subtree respectively (in this case g or m; let's choose g)
- Any children of the replacing node (such as f) now become children of replacing node's parent (in this case, e)

Example before and after replacement: