title: How to return a node, uniformly at random, from a binary search tree?
body: <p>Given a BST (may or may not be balanced) how can one return "any" node uniformly at random? A constraint is you cannot use an external indexing data structure. You must traverse the tree in such a manner that every node has an equal chance of being visited.</p>
  
  <p>This question has me perplexed for quite a while. If we can indeed use an external hashtable/pointers we could just randomize on those and return the corresponding node. However, my colleague has put forth a rather complex variant of the question, where no additional data structures can be used. </p>
  
  <ul>
  <li>A simple random walk with a 50-50 chance of either going L/R doesn't work since the probability of returning a node near the bottom of the tree is much smaller(probabilities compound)</li>
  <li>Even randomly generating a depth <code>d</code> and traversing at most <code>d</code> nodes to return the node (or stopping if it's a leaf) doesn't generate a uniform distribution.</li>
  </ul>
  
  <p><strong>Update</strong>: You cannot have an inorder walk and store the result in an array either.</p>
  
  <p>How can one achieve such a traversal? </p>