Instead of a lock each node, we can assign a lock each trunk

Question: I want to see some give me C code for a correct implementation!

Here's my implementation for insert:

struct Tree {
    Node* root;
    Lock* lock;
}

struct Node {
    int value;
    Node* left;
    Node* right;
    Lock* lock;
}

void insert (Tree* tree, int value) {
    // Create new node
    Node* n = new Node;
    n->value = value;
    n->left = n->right = NULL;

    // Lock global lock in order to prevent race conditions involving        
    // the root
    lock(tree->lock);
    if (tree->root == NULL) { // tree is empty
        tree->root = n;
        unlock(tree->lock);
        return;
    }

    // Find correct location to put new node
    Node* ptr = tree->root;
    lock(ptr->lock); // Grab the lock on the node itself
    unlock(tree->lock);
    while (1) {
        Node* next;
        if (val < ptr->val) {
            if (ptr->left == NULL) {
                ptr->left = n;
                unlock(ptr->lock);
                return;
            } else {
                next = ptr->left;
            }
        } else { // (val >= ptr->val)
            if (ptr->right == NULL) {
                ptr->right = n;
                unlock(ptr->lock);
                return;
            } else {
                next = ptr->right;
            }
        }
        // hand-over-hand locking
        lock(next->lock);
        unlock(ptr->lock);
        ptr = next;
    } 
}

For fine-grain locking in a tree, using intention locks can also improve concurrency by adding information on what each operation is doing: https://en.wikipedia.org/wiki/Multiple_granularity_locking