For example :
Code:
Enter phrases to input to the tree: 

alpha
beta
cappa
nequ
neqi
neqd
neqx
neqp
neqy
neqb
neqc
neql
neqt
peqy
petq

Enter a prefix to find all phrases in the tree that start with it : ne

neqb
neqc
neqd
neqi
neql
neqp
neqt
nequ
neqx
neqy

                                                        petq
                                                peqy
                                        neqy
                                neqx
                        nequ
                                                neqt
                                        neqp
                                                neql
                                neqi
                                        neqd
                                                        neqc
                                                neqb
                cappa
        beta
alpha
The first recursion takes place to find the first node matching the prefix "ne", this I consider as the root of a new tree, a tree containing mostly phrases that match the prefix.

The second recursion is an inorder traversal of the subtree to insert the phrases that match the prefix into a list

The idea behind the algorithm is to isolate the part of the entire tree containing phrases with the same prefix, and then move inorder through the sub_tree inserting only the matches into a list.

The only time matches needs to return a value is when the list has been filled with phrases that have the smae prefix from the sub_tree

The base case for recursion is when I search and find the first node in the tree with a similar prefix. This as far as I see is the root of a subtree with phrases of similar prefix.

I then move to recurse though the subtree inserting only the phrases that match the prefix into the list.
The insert into list function returns the complete list, the matches function then returns the list to the caller.

Code:
list_t *matches (bstree_t *index_tree, char *prefix)
{
	int len, compare;
	bstree_t *sub_tree;
	list_t *list, *sublist;
	
	list = make_empty_list ();
	
	len = strlen (prefix);
	
	if (index_tree == NULL)
	{
		return list;
	}
	else
	{
		compare = strncmp (prefix, index_tree->phrase, len);
		if (compare == 0)
		{
			sub_tree = index_tree;
			list = insert_into_list (list, sub_tree, prefix);
			return list;
		}
		else if (compare < 0)
		{
			sublist = matches (index_tree->left, prefix);
			list = sublist;
		}
		else
		{
			sublist = matches (index_tree->right, prefix);
			list = sublist;
		}
	}
	return list;
}


list_t *insert_into_list (list_t *list, bstree_t *tree, char *prefix)
{
	int len, compare;
	len = strlen (prefix);
	
	if (tree == NULL)
	{
		return list;
	}
	else
	{
		insert_into_list (list, tree->left,prefix);
		if ((compare = strncmp (prefix, tree->phrase, len)) == 0)
		{
			list = insert_at_foot (list, tree->phrase);
		}
		insert_into_list (list, tree->right, prefix);
	}
	return list;
}
Make sense, or sensless?