Validate Three Nodes

• Time : O(n)
• Space : O(n)

using namespace std;

// This is an input class. Do not edit.
class BST {
public:
    int value;
    BST *left = nullptr;
    BST *right = nullptr;

    BST(int value) { this->value = value; }
};

void verifyNodeIsOneOrThree(BST* node, BST* nodeOne, BST* nodeThree, bool& one, bool& three) {
    if(node == nodeOne) {
        one = true;
    }
    if(node == nodeThree) {
        three = true;
    }
}


bool validateThreeNodes(BST *nodeOne, BST *nodeTwo, BST *nodeThree) {
    bool one = false, three = false;
    queue<BST*> q;
    q.push(nodeTwo);

    while(!q.empty()) {
        auto node = q.front(); q.pop();
        if(node->left) {
            verifyNodeIsOneOrThree(node->left, nodeOne, nodeThree, one, three);
            q.push(node->left);
        }
        if(node->right) {
            verifyNodeIsOneOrThree(node->right, nodeOne, nodeThree, one, three);
            q.push(node->right);
        }
    }

    if(one == three) return false;

    if(one) q.push(nodeThree);
    else q.push(nodeOne);

    while(!q.empty()) {
        auto node = q.front(); q.pop();
        if(node->left) {
            if(node->left == nodeTwo)
                return true;
            q.push(node->left);
        }
        if(node->right) {
            if(node->right == nodeTwo)
                return true;
            q.push(node->right);
        }
    }

    return false;
}