DFS without a stack (recursive)

Monday, May 5, 2014

I did a quick search for DFS/BFS without Stack/Queue. I believe I am missing something. I was writing a small method for DFS:



static void DFS(TreeNode41 starting) {
System.out.println(starting.value);

if (starting.left!=null && !starting.left.visited) {
DFS(starting.left);
}

if (starting.right!=null && !starting.right.visited) {
DFS(starting.right);
}

//Reached a leaf
if (starting.left == null & starting.right == null) {
//
}
}


Where TreeNode41, is a Binary node, with left and right references. It does not even need to check for visited, or non visited, when the recursive function has nowhere to go, it pops off, which sort of acts like a stack. This Algorithm traverses a binary tree, in a DFS fashion. However I feel like I am missing something. Is the stack data structure needed when one implements DFS Non-recursively? Or is it that, this algorithm will not work for cyclical graphs or something that's not trees?


Any pointers would be appreciated. Thank you!







http://ift.tt/1mwP5Yi