title: Binary trees: Getting the path of an element from its signature
body: <p>Assume you have a binary tree which classifies images. Each node is a different binary test. When an image is fed to the tree, a unique path through the tree is generated.</p>
  
  <p>A path is described as a binary word which is as long as the depth of the tree.</p>
  
  <p>For instance, for a 2-stage binary tree, an example of path would be (0,1) ((left,right) thus ending in the second leaf of the tree from the left).</p>
  
  <p>We also assume that for any image being fed to the tree, all node tests are executable. Thus, we can define a signature for any image: this signature is a binary word which length is the number of nodes.</p>
  
  <p>For instance, for a 2-stage binary tree, an example of signature would be <code>s = {0,1,1}</code></p>
  
  <p><code>s[i]</code> is the binary result from the test of the ith node.</p>
  
  <p>I am looking for a way to get the path of an image from its signature.</p>
  
  <p>A naive way of doing it would be to jump from index to index of the signature with appropriate decreasing leap length.</p>
  
  <p>However, I wonder if there could be a bitwise calculation which could yield the result (The indexes in the signature can be reorganized if necessary).</p>
  
  <p>Is this possible? If yes, how?</p>