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. ]