title: Functions to convert between depth first and breadth first traversals of a complete tree
body: <p>Problem: Consider a complete k-ary tree with l levels, with nodes labelled by their rank in a breadth first traversal. Compute the list of labels in the order that they are traversed in the depth first traversal. </p>
  
  <p>For example, for a binary tree with 3 levels, the required list is:
  [0 1 3 7 8 4 9 10 2 5 11 12 6 13 14]</p>
  
  <p>One way to do this is to actually construct a tree structure and traverse it twice; The first traversal is breadth first, labelling the nodes 0,1,2,.. as you go. The second traversal is depth first, reporting the labels 0,1,3,7,.. as you go. </p>
  
  <p>I'm interested in a method that avoids constructing a tree in memory. I realize that the size of such a tree is comparable to the size of the output, but I'm hoping that the solution will allow for a "streaming" output (ie one that needs not be stored entirely in memory). </p>
  
  <p>I am also interested in the companion problem; start with a tree labelled according to a depth first traversal and generate the labels of a breadth first traversal. I imagine that the solution to this problem will be, in some sense, dual to the first problem. </p>