To clarify things:
Dynamic memory allocations are made on the Heap and should be deallocated explicitly(allocated by new/malloc deallocated by delete/free)
so the basic rule is:
Every dynamically allocated variable allocated heap memory using free or new will have to be deallocated explicitly by calling free and delete respectively.(exception: Smart pointers)
When to rely on garbage collection and when not?
Simple Answer is in case of C++ NEVER. C++ does not have a garbage collector as Java.
How to judge whether some data structure needs to clean up?
1. Check If the structure is dynamically allocated. If YES then it is candidate for clean up.
2. Read the API doccumentation of API which returns or creates the data structure, to see if the API expects you to de-allocate memory of the data structure.
3. To overcome this problem of explicitly deallocating memory, C++ has special types of implementations called "Smart pointers" using the principle of "RAII". If your data struture is a smart pointer you need not bother about the clean up.
Read more about the smart pointers, lots of threads in here too and I am sure it will help you understand answer to your question.