Most of the concurrent lock-free search trees published in literature do not even give a garbage collection strategy(assuming the implementation language has no automatic garbage collection). But they still claim lock-free or wait-free. They make assumption that memory can be reclaimed using recent techniques provided in the literature. I'm not sure sure if there is a lock-free Malloc. But that is not the problem the algorithm is trying to solve.
And almost all these algorithms use Compare-And-Exchange(CAS) instruction which internally uses locks.
