Untitled

struct TrieNode
{
    struct TrieNode *children[bit_size];

    // isEndOfWord is true if the node represents
    // end of a word
    bool isEndOfWord;
};

// Returns new trie node (initialized to NULLs)
struct TrieNode *getNode(void)
{
    struct TrieNode *pNode =  new TrieNode;

    pNode->isEndOfWord = false;

    for (int i = 0; i < 2; i++)
        pNode->children[i] = NULL;

    return pNode;
}

// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void Insert(struct TrieNode *root, string key)
{
    struct TrieNode *pCrawl = root;

    for (int i = key.length() - 1; i >= 0; i--)
    {
        int index = key[i] - '0';
        if (pCrawl->children[index] == NULL)
            pCrawl->children[index] = getNode();

        pCrawl = pCrawl->children[index];
    }

    // mark last node as leaf
    pCrawl->isEndOfWord = true;
}

// Returns true if key presents in trie, else
// false
typedef long long ll;
long long Search(struct TrieNode *root, string key)
{
    struct TrieNode *pCrawl = root;
    ll res = 0;
    for (int i = key.length() - 1; i >= 0; i--)
    {
        int index = key[i] - '0';
        int deg = i;
        if (pCrawl->children[(index + 1) % 2] != NULL){

            res += (1LL << deg);
            pCrawl = pCrawl->children[(index + 1) % 2];
        }
        else
        {
            pCrawl = pCrawl->children[index];
        }
       // cout << res << '\n';
    }

    return res;
}