title: Strategy to find duplicate entries in a binary search tree
body: <p>I have a BST which has duplicate entries. I am trying to find duplicate entries. Now obviously I can write a dumb algorithm which traverses the whole tree, which is easy.</p>
  
  <p>However, I want to write a more efficient one. Here's what I've done/thought so far:</p>
  
  <p>Assume the following tree.</p>
  
  <pre><code>      10
       /   \
      5    15
     /\    / \
    2  8   10 16
        \    \
         8   12
  </code></pre>
  
  <p>If I want to find all 8's, I will first find the 8 on the left subtree of the 10. To find a duplicate, if it has no right child, is it going to be the left-most node on the right-subtree of the the first parent that is larger than that node (8)? And if it did have a right child, then it can be either in the left most node of its right subtree or the right most node on its left subtree?</p>
  
  <p>Are those all the cases, which can be achieved with a bunch of loops and if-statements?</p>
  
  <p>If not, what's a better approach? Can anyone help?</p>
  
  <p>Thanks</p>
  
  <p>EDIT:
  Actually I just realized it can't be the "left most node" or "right most node". That would find the node that is the next highest value or the previous lowest value. Would it be one node before?</p>
  
  <p>EDIT 2:</p>
  
  <p>Fixed my BST example. It follows the following insertion method:</p>
  
  <pre><code>if (node == null) 
      return new NodeBST&lt;Value&gt;(name, value);
  
  if (node.key().compareTo(name) &gt; 0)
      node.setLeft(insert(node.left(), name, value));     
  else
      node.setRight(insert(node.right(), name, value));
  </code></pre>
  
  <p>This means duplicates will be added to the right of their duplicates.. right?</p>