#include <iostream>
using namespace std;

#include "apstring.h"
#include "apstack.h"

struct AdviceNode
{
    apstring QorA;
    AdviceNode * yes;
    AdviceNode * no;
};

bool IsQuestionNode(AdviceNode * T)
// pre: T is not NULL
// post: returns true if T points to a qeustion node;
//       otherwise returns false
{
    if (T == NULL) return false;  // safety check

    // if any children it's a question node
    
    return T->yes != NULL;
}

void GiveAdvice(AdviceNode * T)
// pre: T is not NULL    
{
    apstring response;
    
    while (IsQuestionNode(T))
    {
	cout << T->QorA << " ";
	cin >> response;
	if (response == "Y") T = T->yes;
	else                 T = T->no;
    }
    cout << t->QorA << endl;
}

bool TracePath(AdviceNode * T, const apstring& movie,
	       apstack<apstring>& pathStack)
// pre: T is not NULL
{
    if (T != NULL)  // be safe
    {
	if (! IsQuestionNode(T))       // leaf node
	{
	    if (T->QorA == movie)
	    {
		pathStack.push(movie);
		return true;		
	    }
	    return false;
	}
	// not leaf node, internal node

	if (TracePath(T->yes, movie, pathStack))
	{
	    pathStack.push(T->QorA + " Yes");
	    return true;
	}
	else if (TracePath(T->no, movie, pathStack))
	{
	    pathStack.push(T->QorA + " No");
	    return true;
	}
	else
	{
	    return false;
	}
    }
}

int main()
{
    return 0;
}