Operations on BSTs

All tree operations can be applied to BSTs

However: JOIN is not safe.

As for a sorted list, in a BST there is a unique position in which to place a new value.

Example: insert 2 in this tree:

Insert a value into a BST:

BSTINSERT(V,T) {
  if T is empty
  then T = create_singleton(V)
  else if V > rootvalue(T)
       then if T's right subtree exists
            then BSTINSERT(V,T's right subtree)
            else T's right subtree = create_singleton(V)
       else if T's left subtree exists
            then BSTINSERT(V,T's left subtree)
            else T's left subtree = create_singleton(V) }