/**
 * 
 */
package tree_graph;

import java.util.LinkedHashMap;
import java.util.Map;

import datastructures.tree.TreeNode;

/**
 * @author Sudharsanan Muralidharan
 */
public class BSTRandom<T> {
  private TreeNode<T> root = null;
  private Map<TreeNode<T>, Integer> treeCount = null;

  public BSTRandom() {
    treeCount = new LinkedHashMap<TreeNode<T>, Integer>();
  }

  public TreeNode<T> insertRoot(T data) {
    root = new TreeNode<T>(data);
    treeCount.put(root, 1);
    return root;
  }

  public TreeNode<T> insert(TreeNode<T> root, T data) {
    TreeNode<T> node = null;
    if (root == null) {
      node = new TreeNode<T>(data);
      treeCount.put(node, 1);
      return node;
    }

    if (root.compareTo(data) > 0) {
      node = insert(root.left, data);
      root.left = node;
    } else {
      node = insert(root.right, data);
      root.right = node;
    }

    treeCount.put(root, treeCount.get(root) + 1);
    return root;
  }

  public TreeNode<T> find(TreeNode<T> root, T data) {
    if (root == null) {
      return null;
    }

    if (root.data.equals(data)) {
      return root;
    } else if (root.compareTo(data) > 0) {
      return find(root.left, data);
    } else {
      return find(root.right, data);
    }
  }

  public void inOrder(TreeNode<T> root) {
    if (root != null) {
      inOrder(root.left);
      System.out.print(root.data + " ");
      inOrder(root.right);
    }
  }
}

@@ -79,16 +79,41 @@
 til.Map;
+%0Aimport java.util.Random;
 %0A%0Aimport
@@ -1267,24 +1267,685 @@
 %0A    %7D%0A  %7D%0A%0A
+  public TreeNode%3CT%3E getRandom(TreeNode%3CT%3E root) %7B%0A    TreeNode%3CT%3E randomNode = randomize(root);%0A    if (randomNode.equals(root)) %7B%0A      return root;%0A    %7D else %7B%0A      return getRandom(randomNode);%0A    %7D%0A  %7D%0A%0A  private TreeNode%3CT%3E randomize(TreeNode%3CT%3E root) %7B%0A    int subTreeCount = treeCount.get(root);%0A    if (subTreeCount == 1) %7B%0A      return root;%0A    %7D%0A%0A    int randomNum = new Random().nextInt(subTreeCount);%0A    if (randomNum == 0) %7B%0A      return root;%0A    %7D else %7B%0A      if (randomNum %25 2 == 0) %7B%0A        return root.left == null ? root.right : root.left;%0A      %7D else %7B%0A        return root.right == null ? root.left : root.right;%0A      %7D%0A    %7D%0A  %7D%0A%0A
   public voi

Add getRandom method in BSTRandom to fetch randomNode