Tree operations so far have involved just one tree.

An operation on two trees:   t = joinTrees(t1,t2)

• Pre-condition:
  • max(key(t1)) < min(key(t2))
• Post-condition:
  • result is a BST (i.e. correctly ordered) with all items from t1 and t2

• find the min node in the right subtree (t2)
• replace min node by its right subtree
• elevate min node to be new root of both trees

Advantage: doesn't increase height of tree significantly

x ≤ height(t) ≤ x+1, where x = max(height(t1),height(t2))

Variation: choose deeper subtree; take root from there.