In this article, we have presented two algorithms to select a random node from Binary Tree while maintaining the uniform randomness.

Table of contents:

1. Introduction to Randomized Algorithms
2. Efficient Approach
3. Second approach : Using ArrayList

Introduction to Randomized Algorithms

In Mathematics , we all have studied about the concept of random events,experiments and the probabilities govering them. For solving the above problem we generally use the concept of Probability and Randomised Algorithm.

Now before jumping at the problem, lets first take a quick glance at the concept of Randomised algorithms in programming.

What is Randomised Algorithm?
An algorithm that takes help of random numbers to decide the upcoming/next action in its logic is called randomised algorithm. The fate of the entire algorithm depends on the random number generated.

There are basically two types of Randomises algorithms :

1. Las Vegas algorithm : Allowed to return only true values
2. Monte Carlo algorithm : Allowed to return wrong values but with small probability.

What is Probability?

The part of Mathematics that deals with finding the chance of the occurence of a random event is called probability. For example , we have a coin , the probability of finding heads on tossing the coin is 0.5. Its general formula is :
P(X) = (No. of favorable outcomes) / (No. of possible outcomes)

1. Efficient Approach :

Let's jump first to the Algorithm :

Step 1: START
Step 2: The first task is to create a Binary tree
(i) Declare a static class(TreeNode in this case) that will basically contain the data and pointers for the left and right child of every root.
(ii) Then create a class with binary tree class(TreeNode as return type that will create new node for our binary tree
Step 3: Declare a method with Binary Tree class as return type that will basically count the number of children for a given root
Step 4: Then we will define a random number generator
(i) randomNode()
index = int index = (int) (Math.random() * (root.child + 1));
Step 5: Having got the random index, we now have to just return the corresponding node of the binary tree
Step 5: STOP

Java Implementation of the Algorithm:

// Program to select a random node from a Binary tree

import java.lang.*;

class Opengenus_random_treeNode
{
static class TreeNode
{
    int val;
    int child;
    TreeNode left, right;
}

static TreeNode Node(int data)
{
    TreeNode temp = new TreeNode();
    temp.val = data;
    temp.left = temp.right = null;   //No child initially for the Binary tree
    temp.child = 0;
    return temp;
}

static int getChild(TreeNode root)
{
    if (root == null)
        return 0;
    return getChild(root.left) +
            getChild(root.right) + 1;
}

// the following function just counts the number of children for a given root
static TreeNode ChildCount(TreeNode root)
{
    if (root == null)
        return null;

    root.child = getChild(root) - 1;
    root.left = ChildCount(root.left);
    root.right = ChildCount(root.right);
    return root;
}

// returns number of children for a particular root of the binary tree
static int children(TreeNode root)
{
    if (root == null)
        return 0;
    return root.child + 1;
}

//The following function is basically used to return the required random node of the binary tree
static int randomNodeUtil(TreeNode root, int count)
{
    if (root == null)
        return 0;

    if (count == children(root.left))
        return root.val;

    if (count < children(root.left))
        return randomNodeUtil(root.left, count);

    return randomNodeUtil(root.right,
            count - children(root.left) - 1);
}

// Returns Random node
static int randomNode(TreeNode root)
{

    int index = (int) (Math.random() * (root.child + 1));
    return randomNodeUtil(root, index);
}


public static void main(String[] asdf)
{
    //Now let's create the binary Tree

    TreeNode root = Node(1);
    root.left = Node(2);
    root.right = Node(3);
    root.left.right = Node(12);
    root.left.right = Node(89);
    root.right.left = Node(68);
    root.right.right = Node(99);
    root.right.left = Node(68);

    ChildCount(root);

    System.out.println( "Random Node : " +
            randomNode(root));
}
}

Output :

1. First Execution :

   Random Node : 89
   

2. Second Execution :

   Random Node : 1
   

3. Third Execution :

   Random Node : 89
   

Explanation of the above approach :
So in this particular solution we have tried to basically modify the structure of the tree. Let's take a ride through an example :

(a) Store the count of children for each node

The value on the left is node and on the right is the count of children

(b) Consider the inorder traversal of the tree and generate a number smaller than or equal to the number of nodes in the tree i.e. random number
(c) Now traverse the tree and visit the desired node using the counts.
(d) On reaching a particular node, we go either to the left subtree or right subtree using the random number, if the random number is less than count then go to the left else to the right, remember that we are moving either to the left or right at a time.
In the above implementation, we use getChild() method to get the count of children for the root, randomNode() method to return the random node of the tree.
Note that the child attribute stores the count of children for each node of the tree.

Time Complexity : O(h), where h is the height of the tree
Auxiliary Space Complexity : O(1)

2. Second Approach : Using ArrayList

Having gone through the above mentioned tedious method, let's jump on to a simple method that will basically make use of a inorder traversal of tree and then we will generate a random number between 0 to n-1, then use the number as array index and display the number at that particular index.

Let's take a look at the algorithm :
Step 1: START
Step 2: First create a binary tree using the steps mentioned in the first approach
Step 3: Now use a method inOrder() that takes a node as input parameter to traverse through the binary tree in inorder fashion as also store the values in a ArrayList simultaneously.
Step 4: Now define a method getrandom() that takes a node as input parameter, in this first call the inOrder() method to store the values in the arraylist, then find the size of the binary tree and now just generate a random number between 0 to n-1.
Step 5: After generating the number display the value of the ArrayList at the generated index
Step 6: STOP

Java implementation of the Algorithm :

import java.util.ArrayList;

// Using auxillary array to find the random node in a given binary tree
class Node {
int item;
Node left, right;

public Node(int key) {
    item = key;
    left = right = null;
}
}

class Tree {

// Using a arraylist to store the inorder traversal of the given binary tree
static ArrayList<Integer> list = new ArrayList<Integer>();
// root of Tree
Node root;

Tree() {
    root = null;
}

// Now lets find the inorder traversal of the given binary tree
static void inOrder(Node node) {
    if (node == null)
        return;

    // traverse the left child
    inOrder(node.left);

    list.add(node.item);
    // traverse the right child
    inOrder(node.right);
}

public void getrandom(Node val)
{
    inOrder(val);
    // getting the count of node of the binary tree
    int n = list.size();
    int min = 0;
    int max = n - 1;
    //Generate random int value from 0 to n-1
    int b = (int)(Math.random()*(max-min+1)+min);
    // displaying the value at the generated index
    int random = list.get(b);
    System.out.println("Random Node : " + random);

}


public static void main(String[] args) {
    Tree tree = new Tree();


    tree.root = new Node(1);
    tree.root.left = new Node(12);
    tree.root.right = new Node(9);
    tree.root.left.left = new Node(5);
    tree.root.left.right = new Node(6);

    tree.getrandom(tree.root);


}
}

Output :

1. First Execution :

   Random Node : 9
   

2. Second Execution :

   Random Node : 1
   

3. Third Execution :

   Random Node : 12
   

Explanation of the approach:
(a) Form the required binary tree
(b) Now use the inOrder() method to get the nodes in inOrder fashion and also store them in the given arraylist list
(c) Using the getRandom() method generate a random number between 0 to n-1, then get the value at the generated random number from the arraylist using get() method and finally display the result.

Time Complexity : O(n), where n is the number of nodes in the tree
Auxiliary Space Complexity : Theta(1)

MCQs on Randomised algorithms

1. Unix sort command uses?
(A) Quick sort
(B) Bucket sort
(C) Insertion sort
(D) Merge sort

Ans : A

2. Which of the following is a type of randomized algorithm?
(A) New York algorithm
(B) California algorithm
(C) Monte Carlo algorithm
(D) Colorado algorithm

Ans : C

3. Which among the follwing can be solved in Computer Science?
(A) NP = co-NP problem
(B) P = NP problem
(C) P = BPP problem
(D) None of these

Ans : A, B, and C

4. Which one of the following algorithm is fast in execution?
(A) Las Vegas algorithm
(B) Duke algorithm
(C) Atlantic City algorithm
(D) None of these

Ans : C

5. Which of the following the application of randomized algorithm?
(A) Quick sort
(B) Min cut
(C) All of the mentioned
(D) Verifying Matrix Multiplication

Ans : C

Thank You!