I think the idea might be similar to sorted linked list case, except two locks are hold for every parent and child nodes.

@gohan, I think this is on the right track, as this prevents two threads from inserting nodes that are children of the same parent/deleting these nodes. One issue might be trying to add/delete at a deep location within the tree while another thread is deleting a grandparent thread - this is a weird situation, but I don't think it introduces any correctness issues?

I think insert is the easier one here (I think just holding lock on the parent node that the inserted node is going to be attached to is enough), but deletion is much more complicated. For example, deletion for a node closer to root requires the program to find the node that needs to be moved up to replace the deleted node, which can be many levels down (see https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/). It looks like we need to hold locks for all the nodes on the path from the node being deleted to the node that would replace the deleted node?

Interesting paper (coauthored by Kunle) on how to solve this efficiently https://stanford-ppl.github.io/website/papers/ppopp207-bronson.pdf

If we don't have to worry about keeping the binary tree balanced, then the two locks solution should be sufficient. However dealing with tree rotations efficiently seems really tricky.