title: convert binary search tree to lists
body: <p>I tried to debug this question: converting a binary search tree to linked lists of all nodes at each level. But I encountered run time error.  In the code, I basically run BFS of the binary search tree and keep track of each level, if a new level hit, I create a new linked list to store the new level's node. I used the STL's linked list to store the nodes. Before that I create a binary search tree using function min_height. I test these methods with input vector={1, 2, 3, 4, 5, 6}. The tree looks like the following picture. It runs well for some nodes, but stop at node 2. I cannot figure out the reason, could someone help me with it? Thank you !<img src="https://i.stack.imgur.com/j33dR.png" alt="enter image description here"></p>
  
  <pre><code>#include &lt;iostream&gt;
  #include&lt;string&gt;
  #include&lt;vector&gt;
  #include&lt;queue&gt;
  #include&lt;list&gt;
  using namespace std;
  
  template&lt;typename Key, typename Value&gt;
  struct BSTNode{
   Key key;
   Value value;
   BSTNode * left;
   BSTNode * right;
   BSTNode(Key k, Value v, BSTNode *l=NULL, BSTNode *r=NULL): key(k), value(v), left(l), right(r) {}
   };
  
  
  template&lt;typename Key, typename Value&gt;
  vector&lt; list&lt;BSTNode&lt;Key, Value&gt;*&gt; &gt; creat_lists(BSTNode&lt;Key, Value&gt;* root){
   vector&lt; list&lt;BSTNode&lt;Key, Value&gt;*&gt; &gt; v;
   if(root==NULL) return v; 
   queue&lt;BSTNode&lt;Key, Value&gt;*&gt; q;   queue&lt;int&gt; level;  int prev;
   q.push(root);   level.push(0);   prev=-1;
   while(!q.empty()){
    BSTNode&lt;Key, Value&gt;* cur=q.front();    int cur_level=level.front();
    cout&lt;&lt;"cur-&gt;key: "&lt;&lt;cur-&gt;key&lt;&lt;" cur_level: "&lt;&lt;cur_level&lt;&lt;endl;
  
    if(prev!=cur_level){
      list&lt;BSTNode&lt;Key, Value&gt;*&gt; l;
      l.push_back(cur);
      v.push_back(l);
    }
    else  {cout&lt;&lt;"got in"&lt;&lt;endl;  v.back().push_back(cur);}
  
    if(cur-&gt;left )cout&lt;&lt;"cur-&gt;left: "&lt;&lt;cur-&gt;left-&gt;key&lt;&lt;endl;
    if(cur-&gt;right )cout&lt;&lt;"cur-&gt;right: "&lt;&lt;cur-&gt;right-&gt;key&lt;&lt;endl;
  
    prev=cur_level;
    if(cur-&gt;left) {q.push(cur-&gt;left);  level.push(cur_level+1); }
    if(cur-&gt;right) {q.push(cur-&gt;right);  level.push(cur_level+1);}
  
  
  
    q.pop();    level.pop();
  
  
   }
  return v;
  }
  
  
  template&lt;typename Key, typename Value&gt;
  BSTNode&lt;Key, Value&gt;* min_height(vector&lt;int&gt; &amp;v, int left, int right ){// here is different from my paper code
    if(left&lt;=right){
      int mid=left+ (right-left)/2;
      BSTNode&lt;Key, Value&gt;* node=new BSTNode&lt;Key, Value&gt;(v[mid], v[mid]);
      node-&gt;left=min_height&lt;Key, Value&gt;(v, left, mid-1 );
      node-&gt;right=min_height&lt;Key, Value&gt;(v, mid+1, right );
      return node;
      }
  }
  
  
  int main(){
    vector&lt;int&gt; v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);  
    BSTNode&lt;int, int&gt;* root=min_height&lt;int, int&gt;(v, 0, 5);
   vector&lt;list&lt;BSTNode&lt;int, int&gt;*&gt; &gt; newv=creat_lists(root);
   //for(int i=0; i&lt;newv.size(); i++)  cout&lt;&lt;(v[i].front())-&gt;key&lt;&lt;endl;
  }
  
  
  
  complier result:
  Run Status: Runtime Error
  
  cur-&gt;key: 3 cur_level: 0
  cur-&gt;left: 1
  cur-&gt;right: 5
  cur-&gt;key: 1 cur_level: 1
  cur-&gt;right: 2
  cur-&gt;key: 5 cur_level: 1
  got in
  cur-&gt;left: 4
  cur-&gt;right: 6
  cur-&gt;key: 2 cur_level: 2
  </code></pre>