title: Implementation of trie with map without creating new nodes
body: <p>I was trying to implement the trie data structure &amp; wrote the foll code</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;string&gt;
  #include&lt;map&gt;
  #include&lt;vector&gt;
  using namespace std;
  
  struct trie_node{
    map&lt;char, trie_node&gt; child;
    int pos=-1;
  };
  
  map&lt;char, trie_node&gt; baap;
  
  void lex_insert(string s, int pos){ // lexiographically insert into map
    trie_node t = baap[s[0]];
    for(int i=1; i&lt;s.size(); i++){
      t = t.child[s[i]];
    }
    t.pos = pos;
  }
  
  int find(string s, int r){  // find in trie structure
    trie_node t = baap[s[0]];
    int pos = t.pos;
    for(int i=1; i&lt;s.size(); i++){
      if(t.child.find(s[i])!=t.child.end()){
        t = t.child[s[i]];
        if(t.pos&lt;=r)
          pos = t.pos;
      }
      else
        return pos;
    }
    return pos;
  }
  
  void ans(int &amp;found, string s){ // find lexiographically matching prefix
    trie_node t = baap[s[0]];
    if(found&lt;0){
      while(t.pos&lt;0){
        auto x = t.child.begin();
        t = x-&gt;second;
      }
      found = t.pos;
    }
  }
  
  int main(){
    int n;  cin&gt;&gt;n;
    vector&lt;string&gt; vs(n);
    for(int i=0; i&lt;n; i++){
      cin&gt;&gt;vs[i];
      lex_insert(vs[i],i);
    }
    int found = 0;
    int q;  cin&gt;&gt;q;
    for(int i=0; i&lt;q; i++){
      int r; string p;
      cin&gt;&gt;r&gt;&gt;p;
      found = find(p,r);
      ans(found, p);
      cout&lt;&lt;vs[found]&lt;&lt;'\n';
    }
  }
  </code></pre>
  
  <p>Please focus on <code>lex_insert()</code> 
  The code executes without errors, though when I try to dereference the map - <code>baap</code>, there are segmentation fault showing up. I guess this is because I didnt construct new nodes at each level in <code>lex_insert</code> as I have seen in some codes. But then, map is supposed to do dynamic allocation. Can someone please explain, why I am not able to access the elements of map - <code>baap</code> ?</p>
  
  <p>Note - Its not an exact trie implementation but derives from it</p>