Efficient way to check if a graph node's children were visited during traversal I have a generic traversal algorithm for graphs:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
    }
}


and I want to make a time-efficient "child head count" for nodes that sets a flag for nodes whenever all their children have been visited:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        set close flag on parent nodes if last child to be visited
    }
}


The best ways that i could think of was to have pointers to "visited" booleans of the node's children and just "and" them up as such:

node1 -&gt; [node2(true), node5(false), node7(true)]

node1.all_children_visited() = false


Or iterate through the parents whenever I visit the node for the first time:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        if first visit {
            for each parent {
                increase count
                if count(parent) = number of children {close(parent)}
            }
            if count(this) = number of children {close(this)}
        }
    }
}


Is there a way to do this with lower than O(n) complexity?
If you can afford more memory, add a field to each node's data containing a count of already visited children. Assuming that you know the number of children, if you update this field each time you visit a child, you will know when all children have been visited.