Question

Question 1:

For rooted trees, like binary trees, why do people make sure never to push NULL/nil/null onto the stack?

e.g.

while(!stack.empty() ) {
    x = stack.pop();
    visit(x);

    if(x->right) stack.push(x->right);
    if(x->left) stack.push(x->left);
}

instead of

while(!stack.empty() ) {
    x = stack.pop();
    if(!x) continue;

    visit(x);
    stack.push(x->left), stack.push(x->right);
}

I mean, the second form more naturally aligns with the recursive form of preorder/DFS, so why do people use the "check before" with iterative usually, and "check after" with recursive? Any reason I am missing, other than saving (n+1) stack spots (which doesn't add to the space complexity)?

Question 2:

DFS on Graph: Using iterative, why do people set visited flag when pushing adjacent nodes of current node, but in recursive, we only do it after the recursion takes place?

e.g. iterative:

while(!stack.empty()){

    x=stack.pop();
    // we do not need to check if x is visited after popping

    for all u adjacent from x          
        if(!visited[u]) stack.push(u), visited[u]=true; //we check/set before push

}

but in recursive:

void DFS(Graph *G, int x)
{
    if( !visited[x] ) return; //we check/set after popping into node
    visited[x]=true;

    for all u adjacent from x
        DFS(G, u);   //we do not check if u is already visited before push
 }

SO in general, the connection between two questions is: Why we are more careful before pushing valid things onto an actual stack object (iterative methods of DFS), but are less careful when using the hardware stack (recursive)? Am I missing something? Isn't the hardware stack more of a "luxury" because it can overflow (for stack objects, we can declare them off heap) ?

Thank you kind people for the insights.

[ This is not simply coding style, this is about total rearrangements of how algorithms are coded. I'm talking about being careless with harware stack vs. being careful with software stack? I'm also wondering about some technical differences (i.e., are they truly equal methods for all situations). And almost all books follow above patterns. ]

No correct solution

OTHER TIPS

Check when you push or when you pop is both OK, but check when you push perform better,

For example if you have a binary tree of depth 10, if you check when you pop, you are basically traversing a tree of depth 11(It's like you added added two more NULL Children to each leaf) thats 2048 more wasted operation. If its recursive then it means it will make 2048 more none necessary function call.

Other than that it's OK to check before or after, it's just happened that the code you saw been written that way.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top