Random Node

4.11 Random Node: You are implementing a binary search tree class from scratch, which, in addition to insert, find, and delete, has a method getRandomNode() which returns a random node from the tree. All nodes should be equally likely to be chosen. Design and implement an algorithm for getRandomNode, and explain how you would implement the rest of the methods.

• My getRandNode assumes that our bst has kept track of the max level. I use this variable to indicate to the tree how far we should go down as a random index.

• Then, whilst tranversing the tree recursively, I keep track of this count, and simply join a random left or right.

Node* tranverseRand(Node *root, int level, int count) {
    if (level <= count) return root;

    cout << root->value << endl;
    pause();
    srand(time(nullptr));
    bool direction = rand() % 1;

    if (root->right && direction) 
        tranverseRand(root->right, level, ++count);

    else if(root->left && !direction) 
        tranverseRand(root->left, level, ++count);

    // otherwise just take the path that exists
    else if (root->right)
        tranverseRand(root->right, level, ++count);

    else
        tranverseRand(root->left, level, ++count);
}


Node* getRandomNode(Node *root, int maxLevel) {
    if (!root) return nullptr;

    srand(time(nullptr));
    int level = rand() % maxLevel; // [0 - maxLevel]
    return tranverseRand(root, level, 0);
}

• However, while this approach is fast, it doesnt represent the nodes equally. It would if the left and right sides were the same size, but it is likely not the case. We cannot have left and right be chosen on a 50/50 likelyhood. If the left side contains more nodes, it would be represented as more likely to go left.

• To fix this, what we can do is maintain the size of the left and right subtree PER node. At this point, we would then be able to rightfully balance the probabilities of the left and right subtrees.

Node* tranverseRand(Node *root, int level, int count) {
    if (level <= count) return root;

    bool direction = rand() % root->size;

    if (root->right && direction > root->leftsize) 
        tranverseRand(root->right, level, ++count);

    else if(root->left && direction <= root->leftsize)
        tranverseRand(root->left, level, ++count);

    // otherwise just take the path that exists
    else if (root->right)
        tranverseRand(root->right, level, ++count);

    else
        tranverseRand(root->left, level, ++count);
}


Node* getRandomNode(Node *root, int maxLevel) {
    if (!root) return nullptr;

    srand(time(nullptr));
    int level = rand() % maxLevel; // [0 - maxLevel]
    return tranverseRand(root, level, 0);
}

Node* tranverseRand(Node *root, int level, int count) {
    if (level <= count) return root;

    bool direction = rand() % root->size;

    if (root->right && direction > root->leftsize) 
        tranverseRand(root->right, level, ++count);

    else if(root->left && direction <= root->leftsize)
        tranverseRand(root->left, level, ++count);

    // otherwise just take the path that exists
    else if (root->right)
        tranverseRand(root->right, level, ++count);

    else
        tranverseRand(root->left, level, ++count);
}


Node* getRandomNode(Node *root, int maxLevel) {
    if (!root) return nullptr;

    srand(time(nullptr));
    int level = rand() % maxLevel; // [0 - maxLevel]
    return tranverseRand(root, level, 0);
}

• An a lot simpler approach would be to just tranverse (any traversal) the tree until we reach a random index n. Where n is 0 % size_tree.

int getRandomInt(int size) {
    srand(time(nullptr));
    return rand() % size; // [0 - size]
}

Node* getRandomNode(Node *root, int count, int goTo) {
    if (count >= goTo) {
        return root;
    }
    else {
        // arbitrary traversal, chose in order
        if (root->left) {
            getRandomNode(root->left, ++count, goTo);
        }
        if (root->right) {
            getRandomNode(root->right, ++count, goTo);
        }
    }
}

/*
Node *rand_n = t->getRandomNode(t->getRoot(), 0, t->getRandomInt(t->size));
cout << rand_n->value << endl;
pause();
*/