Answer to Question 39B-4

  List mems(ConstTree T, List L)
  {
    if(T == NULL)
    {
      return L;
    }
    else
    {
      List B = mems(T->right, L);
      List A = mems(T->left, B);
      return cons(T->item, A);
    }
  }

Look at the example where L is [4, 5, 6] and T is

you know that the answer is [9, 2, 0, 7, 1, 8, 4, 5, 6].

1. List B is [7, 1, 8, 4, 5, 6], the list of all members of the right subtree of T followed by L.

2. List A is [2, 0, 7, 1, 8, 4, 5, 6], the list of all members of the left subtree of T followed by B.

3. The result is 9:A = [9, 2, 0, 7, 1, 8, 4, 5, 6].