# 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.

```cpp
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.&#x20;

```cpp
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.

```cpp
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();
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/interview_questions/random-node.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.