This code seems broken, though. The big challenge with these kinds of lock-free parallel algorithms is always how to deal with lifetimes and prevent use-after-frees (unless you never want to free anything from this tree, which seems a bit unlikely).
The fundamental problem is that nothing prevents a reader from dereferencing a node the writer has free()'d. Fixing this requires either adding RCU or Hazard pointers.
The fundamental problem is that nothing prevents a reader from dereferencing a node the writer has free()'d. Fixing this requires either adding RCU or Hazard pointers.