Tree with probability

Randomly generate a node

Solution I : serialize the tree into a dll, and using random generator

unknown size : reservior sampling

Code Implementation

Code I : 
    TreeNode sample = null;
    int count = 0;
    //return type : number of size of subtree rooted at root
    int findSample(TreeNode root) {
        if (root == null) {
            return 0;
        }
        count++;
        int r = random(count);
        if (count == 0) {
            sample = root;
        }
        findSample(root.left);
        findSample(root.right);
    }

Code II : 
  //without using global variable
  //count : number of nodes have traversed before visiting root.
  int findSample(TreeNode root, int count) {
      if (root == null) {
          return count;
      }
      count++;
      int r = random(count);
      if (count == 0) {
          sample = root;
      }
      int lc = findSample(root, count);
      findSample(root.right, lc);
      return lc;
  }

Method II Divide and Conquer

qs.