0 1 Trie - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int,int>
const int N=3e5+5,MAX_BIT=29;
 
struct node{
    node* edges[2];
    int end;
 
    node(){
        this->edges[0] = this->edges[1] = nullptr;
        this->end = 0;
    }
};
 
void insert(int x, node* n, int l=MAX_BIT){
    if(l==-1)
        n->end++;
    else{
        int i=0;
        if(x&(1<<l)) i=1;
        if(n->edges[i]== nullptr){
            node* p = new node;
            n->edges[i]=p;
        }
        insert(x,n->edges[i],l-1);
    }
}
 
int find(int x, node* n, int l=MAX_BIT){
    if(l==-1) return n->end;
    int i=0;
    if(x&(1<<l)) i=1;
    if(n->edges[i]!= nullptr){
        return find(x,n->edges[i],l-1);
    }else return 0;
}
 
bool Delete(int x, node* n, int l=MAX_BIT){
    if(l==-1){
        n->end--;
        if(n->edges[0]!= nullptr || n->edges[1]!= nullptr || n->end){
            return false;
        }else return true;
    }else {
        int i=0;
        if(x&(1<<l)) i=1;
        if(n->edges[i]== nullptr) return false;
        bool del=Delete(x, n->edges[i], l - 1);
        if(del){
            auto p = n->edges[i];
            n->edges[i]= nullptr;
            delete p;
        }
        if(n->edges[0]!= nullptr || n->edges[1]!= nullptr || n->end) return false; else return del;
    }
}