title: Making a list of lists in scheme using datatypes and recursion
body: <p>I am currently learning Scheme and have just learned about inductive sets and recursion. I currently defined a datatype bTree which is a binary tree</p>
  
  <pre><code>(define-datatype bTree bTree?
    (leaf
      (datum number?))
    (node
      (value symbol?)
      (left bTree?)
      (right bTree?)))
  </code></pre>
  
  <p>Which works fine. I want to create a function that when given a bTree, would return a list of paths from the root (which are also lists), to each of the leaves, in which left is indicated by a 0 and right is indicated by 1. </p>
  
  <pre><code>(define bTree-path
    (lambda (tree)
  (cases bTree tree
    (leaf (datum) '())
    (node (value left right)
            (list (cons 0 (bTree-path left)) (cons 1 (bTree-path right)))))))
  </code></pre>
  
  <p>My thought process was that if it sees a leaf, it returns nothing to the current list. However if it is a node, a new list is created. In this list the function is called recursively for both left and right subtrees with a cons operator with 0 and 1 respectively (meaning on step left and one step right). This quickly was proven wrong as the result for a test tree included nested lists. The result should be something like ( (0 1) (0 0) (1) ) which means there are 3 leaves that can be found by going left twice, right once or left and then right. </p>
  
  <p>Working from the leaves to the root will not work because you will not know what whether the leaf is a left or right leaf. Calling list everytime a node is found is causing the nesting. Is there a way that can simply call two lists at the same time using two recursive calls with left and right subtrees? Possibly a function or operation?</p>