Making a list of lists in scheme using datatypes and recursion

Question

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

(define-datatype bTree bTree?
  (leaf
    (datum number?))
  (node
    (value symbol?)
    (left bTree?)
    (right bTree?)))

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.

(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)))))))

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.

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?

molbdnilo molbdnilo · Accepted Answer · 2016-02-06T09:15:37

Since the result of (bTree-path left) is (or at least it should be) a list of all the paths from left to the leaves in that subtree, you need to add 0 to each one of those paths.
Likewise for the right subtree.

The function that does something to each element of a list is map:

(map (lambda (path) (cons 0 path)) (bTree-path left))

Next, you want to merge your two lists of paths – from the left and from the right – into one list, and the function that does that is append.

Putting it all together left as an exercise.

Making a list of lists in scheme using datatypes and recursion

1 Answers