Maintaining context of current node in a iterative DFS vs a recursive DFS

I am facing a problem, where I am looking for a special type of node in a graph. The algorithm works in following way:

bool findSpecial(Node n)
{
    if(isSpecial(n))
        return true;

    bool isSpecial = false;
    vector<Node> childs = getChildren(n);
    foreach(child, childs)
    {
       isSpecial |= findSpecial(child);
    }

    if(isSpecial)
      markCurrentNodeSpecial(n);

    return isSpecial;
}

Above is a template of the algorithm, assuming that the input is DAG. It looks for special nodes in the graph and marks current node special if any node in its the DFS tree is special.

The algorithm is basically populating this special attribute wherever it is reachable.

It can however lead to Stack Overflow in some rare cases.

I am trying to figure out if the same thing can be done iteratively or not. The problem with iterative approach is that the information whether all the children of a Node are processed is not readily available.

Any suggestion?

1. The simplest solution - would std::stack<Node> work? You should make it work like a program stack works - push the starting Node there, then pop a node, check if it's special, if not - push its children, repeat.

2. You don't check if you have already visited a node - maybe you can speed it up a bit. (Edited: I can't read)

Update: yes, this was an interesting beast. How about this code? I didn't test it though, but the main idea should work: split visitation into two steps - before and after recursion.

struct StackNodeEntry
{
    Node cur;
    optional<Node> parent;

    enum class Pos
    {
        before_recursion, after_recursion
    } pos;
};

bool findSpecial(Node root)
{
    stack<StackNodeEntry> stack;

    stack.push({ root, {}, StackNodeEntry::Pos::before_recursion });

    while (!stack.empty())
    {
        auto& e = stack.top();

        switch (e.pos)
        {
        case StackNodeEntry::Pos::before_recursion:
            if (isSpecial(e.cur))
            {
                if (e.parent)
                    markCurrentNodeSpecial(*e.parent);
                stack.pop();
                break;
            }

            e.pos = StackNodeEntry::Pos::after_recursion;
            for (auto n : getChildren(e.cur))
                stack.push({ n, e.cur, StackNodeEntry::Pos::before_recursion });

            break;

        case StackNodeEntry::Pos::after_recursion:
            
            if (isSpecial(e.cur))
            {
                if (e.parent)
                    markCurrentNodeSpecial(*e.parent);
            }
            stack.pop(); // don't use e below this line
            break;
        }
    }

    return isSpecial(root);
}