Randomly select a node from a Binary Tree

Question

My tree class:

public class BT<E>{
   E value;
   BT<E> left, right;

   public BT(E value)
   {
      this.value=value;
   }   

   public BT (E value, BT left, BT right) 
   {
      this.value = value;
      this.left = left;
      this.right = right;
   }

How would I go about returning a random node from a tree after I have generated a tree? I know the depth and the number of nodes for every tree I generate.

Answer 1

The algorithms from Dennis and Jeroen are simple to implement but O(n). I believe I have a O(log n) algorithm that is slightly more complicated.

Every node needs an equal chance of being selected. So at some tree T, let LN(T) be the number of nodes in the left tree, RN(T) be the number of nodes in the right tree, and N(T) be the number of total nodes, including this one (so N(T) = 1 + LN(T) + RN(T)). Select a random number R from 0 to N(T) - 1. If R == 0, return this node. If 1 <= R <= LT(N), recurse this method on the left subtree. Otherwise, recurse this method on the right subtree.

Untested code (assuming BT has a .size() method that works in O(1)):

public BT randomNode() {
    int r = new Random().nextInt(this.size());
    if (r == 0) {
        return this;
    } else if (left != null && 1 <= r && r <= left.size()) {
        return left.randomNode();
    } else {
        return right.randomNode();
    }
}

And of course you can do things like hoist the new Random() out of the method but the algorithm is the same.

Edit: fixed null pointer exception when left subtree was null.