This code creates and inserts a new record with key equal to keyvalue as the successor of the record pointed to by pred. It replaces the correct null subtree of pred by the new record, which becomes a terminal node.
p = malloc(sizeof(binarytreenode));
p->key = keyvalue;
p->leftptr = NULL;
p->rightptr = NULL;
if (keyvalue < pred->key)
pred->leftptr = p;
else
pred->rightptr = p;