title: Traversing a Binary Tree with multiple threads
body: <p>So I'm working on a speed contest in Java. I have (number of processors) threads doing work, and they all need to add to a binary tree. Originally I just used a synchronized add method, but I wanted to make it so threads could follow each other through the tree (each thread only has the lock on the object it's accessing). Unfortunately, even for a very large file (48,000 lines), my new binary tree is slower than the old one. I assume this is because I'm getting and releasing a lock every time I move in the tree. Is this the best way to do this or is there a better way?</p>
  
  <p>Each node has a ReentrantLock named lock, and getLock() and releaseLock() just call lock.lock() and lock.unlock();</p>
  
  <p>My code:</p>
  
  <pre><code>public void add(String sortedWord, String word) {
  
      synchronized(this){
          if (head == null) {
              head = new TreeNode(sortedWord, word);
              return;
          }
          head.getLock();
      }
  
      TreeNode current = head, previous = null;
      while (current != null) {
  
          // If this is an anagram of another word in the list..
          if (current.getSortedWord().equals(sortedWord)) {
              current.add(word);
              current.releaseLock();
              return;
          }
          // New word is less than current word
          else if (current.compareTo(sortedWord) &gt; 0) {
              previous = current;
              current = current.getLeft();
              if(current != null){
                  current.getLock();
                  previous.releaseLock();
              }
          }
          // New word greater than current word
          else {
              previous = current;
              current = current.getRight();
              if(current != null){
                  current.getLock();
                  previous.releaseLock();
              }
          }
      }
  
      if (previous.compareTo(sortedWord) &gt; 0) {
          previous.setLeft(sortedWord, word);
      }
      else {
          previous.setRight(sortedWord, word);
      }
      previous.releaseLock();
  }
  </code></pre>
  
  <p>EDIT: Just to clarify, my code is structured like this: The main thread reads input from a file and adds the words to a queue, each worker thread pull words from the queue and does some work (including sorting them and adding them to the binary tree).</p>