It is a well-known task to answer whether a node is an ancestor to another one with time complexity O(n) for preprocessing and O(1) for a query.

Each time you enter the node in recursive function DFS, you increase the time counter by one and call it an "entrance" time, and after recursively processing its sons, you increase the time counter by one and call it an "exit" time. Here is the pseudocode.

DFS(u, p): // u is the current node, p is its parent
    increase the timer counter
    in[u] = timer
    for all (u, v) in edges:
        if v != p:
            DFS(v, u)
    increase the timer counter
    out[u] = timer

Now u is an ancestor of v .

Is there someway to implement the same algorithm but with non-recursive DFS?