These data types are stored in SQLITE databases. Typically, when a user selects to delete one of these data types, the corresponding database entry is dropped from the appropriate database. However, any text associated with that entry may still persist, without structure, in the database's free space until the phone decides to cleanup and vacuum the database.
If you have a physical image from an Android device, you can right-click these SQLite files and select "Parse Database for Deleted Data" to carve for deleted data within them.
The "Deleted" button in the Main toolbar can also be used as a shortcut to automatically find and carve the appropriate SQLite files for deleted SMS and Call History. However, this shortcut may not work with all devices.