Multithreaded Insertion in Binary Search Tree (BST)
<p>I have a task of inserting multiple elements into a BST. The task has to be optimized by use of multiple threads. There is no limit on how many threads can be launched. </p>

<p>Here is my approach. This is a theoretical approach. I have not tried implementing it and have no idea to what extent it will work. Please suggest your opinions on this idea.</p>

<p>The BST Node will look something like this:</p>

<pre><code>class BSTNode {
    int val;
    BSTNode left, right;
    boolean leftLock, rightLock;
    Queue&lt;BSTNode&gt; leftQ, rightQ;
}
</code></pre>

<p>I am not using any Java locks, rather using two boolean variables to denote the state of lock. </p>

<p>Since insertion of any element first requires us to find the relevant position, this task can be carried out in parallel, since this will not modify the tree. The task can only work till the point a node on the path is unlocked. If a particular node is locked, then that particular insertion thread is put to <code>sleep()</code> and added to the corresponding left or right queue and waked up again when lock is released. </p>

<p>On the other hand, if none of the nodes on the path have a lock on them, we can proceed ahead with insertion. Before insertion and modifying the corresponding pointer of parent, a lock must be acquired on the parent.</p>

<p>Can anyone suggest their views on this implementation method?</p>