Randomly select a node from a Binary Tree

So use a Random Integer method and return an integer between 0 and the tree size.

Then do a breadth / depth first traversal on the tree, with a counter, that returns the node when it reaches the random integer.

Random rand = new Random();
int randomNum = rand.nextInt(treesize);
int count = -1;
Node randNode;

public static void getRandomTraversal(Node root){

    count++;

    if(count == randomNum)
        randNode = root;

    if(root.leftChild != null)
        getRandomTraversal(root.leftChild);

    if(root.rightChild != null)
        getRandomTraversal(root.rightChild);
}

Alternatively you could remove count as being global and add it as an argument to the recursive function. Though this is not as easy with binary trees when the tree has more than one child.

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.

1. Select a random number (new Random().nextInt(numberOfNodes))
2. Walk through your tree however your like (depth first, breadth first, postorder, inorder, preorder)
3. For each node you visit, increment a counter
4. If the counter's value equals the randomly chosen number, pick that node