Backend Developer

DFS can be used to detect cycle in an undirected graph. Do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph.

If we don’t find such an adjacent for any vertex, we say that there is no cycle.

Pseudocode :

DetectCycle(graph, v, visited[], parent)
{
	// mark the current node as visited
	visited[v] = true;
	// do for every edge (v, w)
	for (w: graph[v])
	{
		// if `w` is not visited yet
		if (!visited[w])
		{
			if (DetectCycle(graph, w, visited, v)) {
				return true;
			}
		}
		// if `w` is visited, and `w` is not a parent
		else if (w != parent)
		{
			// back-edge (cycle) found
			return true;
		}
	} 
	// No back-edges were found in the graph
	return false;
}

This problem can be solved using two stacks.
Assume the two stacks are current: currentlevel and nextlevel. We would also need a variable to keep track of the current level order(whether it is left to right or right to left). We pop from the currentlevel stack and print the nodes value. Whenever the current level order is from left to right, push the nodes left child, then its right child to the stack nextlevel. 
Since a stack is a LIFO(Last-In-First_out) structure, next time when nodes are popped off nextlevel, it will be in the reverse order. On the other hand, when the current level order is from right to left, we would push the nodes right child first, then its left child. Finally, do-not forget to swap those two stacks at the end of each level(i.e., when current level is empty)