#include <iostream>
#include <stack>
#include "tree.h"
#include "LList.h"
#include "Graph.cpp"
using namespace std;

bool doYouHaveTheWay(graph<char> g, stack<char> st) {
    bool res = true;
    while (st.size() > 1)
    {
        char b = st.top();
        st.pop();
        char a = st.top();
        if(!g.hasEdge(a, b))
            res = false;
    }
    return res;
}

void checkTreeWays(graph<char> const& g,tree<char> const& t, stack<char>& st, bool& res)
{
    if (t.rootTree())
    {
        st.push(t.getRoot());

        if (!t.leftTree().rootTree() && !t.rightTree().rootTree()) {
            if (doYouHaveTheWay(g, st)) {
                res = true;
                return;
            }
        }

        else {
            checkTreeWays(g, t.leftTree(),st,res);
            checkTreeWays(g, t.rightTree(),st,res);
        }
        st.pop();
    }
}

bool finalCheck(graph<char> const& g, tree<char> const& t, stack<char>& st) {
    bool res = false;
    checkTreeWays(g, t, st, res);
    return res;
}


int main() {
    tree<char> d;
    d.create();
    /*
        a
        y
        e
        y
        d
        y
        b
        n
        n
        n
        y
        g
        n
        n
        y
        f
        n
        y
        c
        y
        h
        n
        n
        n
    */
    stack<char> st;
    graph<char> g;
    g.addVertex('a');
    g.addVertex('b');
    g.addVertex('c');
    g.addVertex('d');
    g.addVertex('e');
    g.addVertex('f');
    g.addVertex('g');
    g.addVertex('h');
    g.addEdge('a', 'd');
    g.addEdge('a', 'f');
    g.addEdge('b', 'h');
    g.addEdge('c', 'h');
    g.addEdge('d', 'e');
    g.addEdge('e', 'h');
    g.addEdge('f', 'h');
    g.addEdge('f', 'c');
    g.addEdge('g', 'e');
    g.addEdge('g', 'b');

    cout << finalCheck(g, d, st) << endl;

    system("pause");
    return 0;
}