title: Comparison function for DFS ordering of an arbitrary tree
body: <p>Imagine a complete binary tree where nodes at each level of depth are numbered left to right.</p>
  
  <ul>
  <li>Node 1 has children 2 and 3.</li>
  <li>Node 2 has children 4 and 5.</li>
  <li>Node 3 has children 6 and 7.</li>
  </ul>
  
  <p>etc.</p>
  
  <p>At depth D there will be 2^D nodes, with numbers 2^D ...  2^(D+1)-1</p>
  
  <p>The depth-first search traversal for a complete tree of any depth is deterministic.</p>
  
  <p>For example, a tree of depth 4 will always be traversed:
  1,2,4,8,9,5,10,11,3,6,12,13,7,14,15.</p>
  
  <p>I am looking for a way to sort a list of numbers by where they would fall in the DFS traversal of any tree.</p>
  
  <p>In particular, I would like a comparison function that could take two numbers and determine which comes first in the DFS traversal.</p>
  
  <p>Any ideas?</p>
  
  <hr>
  
  <p>Pre-computing the DFS traversal for some maximum tree size is one way to do this, but I would prefer a mathematical solution that doesn't require computing and storing that information.</p>