List mems(const Tree 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
9
/ \
/ \
2 7
/ / \
0 1 8
you know that the answer is [9, 2, 0, 7, 1, 8, 4, 5, 6].
List B is [7, 1, 8, 4, 5, 6], the list of all members of the right subtree of T followed by L.
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.
The result is 9:A = [9, 2, 0, 7, 1, 8, 4, 5, 6].