Бор для автодополнения: как по узлу быстро отдать все слова с данным префиксом?

Два сценария.

Если нужно только количество слов с префиксом — заведите в каждом узле счётчик cnt, увеличивая его при вставке вдоль всего пути. Тогда ответ — cnt узла, до которого довёл префикс, за O(|prefix|).

void insert(const string& s){
    int v=0;
    for(char ch:s){ int c=ch-'a';
        if(t[v].next[c]==-1){t[v].next[c]=t.size(); t.emplace_back();}
        v=t[v].next[c]; t[v].cnt++;          // считаем проходящие через узел слова
    }
    t[v].leaf=true;
}
int count_prefix(const string& p){
    int v=0;
    for(char ch:p){ int c=ch-'a'; if(t[v].next[c]==-1) return 0; v=t[v].next[c]; }
    return t[v].cnt;
}

Если нужны сами слова — дойдите до узла префикса (O(|prefix|)), затем сделайте DFS по поддереву, накапливая символы и выписывая слово в каждом leaf. Это O(|prefix| + суммарная длина выданных слов) — оптимально, ведь вы обязаны хотя бы напечатать ответ.

void dfs(int v, string& cur, vector<string>& out){
    if(t[v].leaf) out.push_back(cur);
    for(int c=0;c<26;++c) if(t[v].next[c]!=-1){
        cur.push_back('a'+c); dfs(t[v].next[c], cur, out); cur.pop_back();
    }
}

DFS по детям 0..25 даёт слова сразу в лексикографическом порядке — удобно для подсказок.