CareerCup

private static void dfs() {
 
  g.vertexList[0].isVisited = true;
  g.displayVertex(0);
  g.thStack.push(0);
  while (!g.thStack.isEmpty()) {
   int v=getAdjUnVisitedVertex(g.thStack.peek());
   if(v==-1)
   {
    g.thStack.pop();
   }
   else
   {
    g.vertexList[v].isVisited=true;
    g.displayVertex(v);
    g.thStack.push(v);
   }
  }
  for(int j=0;j<g.vertexCount;j++)
   g.vertexList[j].isVisited=false;

 }

Let assume that you are given class Graph and source vertex: (i) push the source to the stack and mark it as visited, (ii) unless stack is empty, pop the vertex, if not visited add its adjacent vertices to the stackan mark as visited.

public void dfs(Graph G, int source) {
	boolean[] isVisited = boolean[G.V()];
	Stack<Integer> stk = new Stack<Integer>();
	stk.push(source);
	isVisited[source] = true;

	while (!stk.isEmpty()) {
		int v = stk.pop();
		for (int w : G.adjacent(v))
			if (!isVisited[w]) {
				isVisited[w] = true;
				stk.push(w);
			}
	}
}

Now the question is what the interviewer wanted you to do with the dfs.

Can someone please point out if there are any logical errors in this algorithm. Thank you!!

public static boolean DFS(Node A, Node root){
		if(root.data == null) return false;
		if(root.data == A.data) return true;
		
		root.visited = true;
		
		for(Node x: root.adjecent()){
			if(x.visited != true){
				DFS(A, x);
			}
		}
                return false;
	}

Here is my implementation of dfs in non-recursive way

private void dfs(int source, int n, LinkedList<Integer>[]g){
	boolean []visited = new boolean[n];
	Stack<Integer> stack = new Stack<Integer>();
	visited[source] = true;
	stack.push(s);

	while(stack.size() > 0){
		int v = stack.peek();
		if (g[v].hasNext()){
			int u = g[v].next();
			visited[u] = true;
			stack.push(u);
		}else{
			stack.pop();
		}
	}
}

static void DFS(TreeNode node) {
			
		Stack stack = new Stack();
		stack.push(node);
		
		while(!stack.isEmpty()) {
			
			while(node.left!=null) {
				if(node.left!=null) {
					stack.push(node.left);
					node = node.left;
				}
			}
			
			while(true) {
				if(stack.isEmpty())
					break;
				TreeNode n = (TreeNode) stack.pop();
				System.out.println(n.data+" ");
				if(n.right!=null) {
					
					stack.push(n.right);
					n = n.right;
					break;
				}
				
				
				
			}
			
		}
		
	}

Here is my Code

/**
*
*/
package com.unmetric.others;

import java.util.Stack;

/** @author User */
public class rg1 {

/** @param args */
public static void main(String[] args) {
dfsPreOrder(getRoot());
System.out.println("---------Pre Order");
dfsInOrder(getRoot());
System.out.println("---------In Order");
dfsPstOrder(getRoot());
System.out.println("---------Post Order");
dfsStackPreOrder(getRoot());
System.out.println("---------with statck Pre Order");
dfsStackInOrder(getRoot());
System.out.println("---------with statck In Order");
dfsStackPstOrder(getRoot());
System.out.println("---------with statck Post Order");
}

private static Node getRoot() {
final Node root = new Node(7);
final Node lvl1Lft = new Node(3);
final Node lvl1Rgt = new Node(9);
root.leftNode = lvl1Lft;
root.rightNode = lvl1Rgt;
lvl1Lft.leftNode = new Node(1);
lvl1Lft.rightNode = new Node(4);
return root;
}

private static void dfsPreOrder(Node node) {
if (node == null) { return; }
System.out.print(node.i);
dfsPreOrder(node.leftNode);
dfsPreOrder(node.rightNode);
}

private static void dfsInOrder(Node node) {
if (node == null) { return; }
dfsInOrder(node.leftNode);
System.out.print(node.i);
dfsInOrder(node.rightNode);
}

private static void dfsPstOrder(Node node) {
if (node == null) { return; }
dfsPstOrder(node.leftNode);
dfsPstOrder(node.rightNode);
System.out.print(node.i);
}

private static void dfsStackPreOrder(Node root) {
final Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
final Node currNode = stack.peek();
if (!currNode.leftVisited || !currNode.rightVisited) {
if (currNode.leftNode != null && !currNode.leftVisited) {
System.out.print(currNode.i);
currNode.leftVisited = true;
stack.push(currNode.leftNode);
} else if (currNode.rightNode != null && !currNode.rightVisited) {
currNode.rightVisited = true;
stack.push(currNode.rightNode);
} else {
System.out.print(currNode.i);
stack.pop();
}
} else {
stack.pop();
}
}

}

private static void dfsStackInOrder(Node root) {
final Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
final Node currNode = stack.peek();
if (!currNode.leftVisited || !currNode.rightVisited) {
if (currNode.leftNode != null && !currNode.leftVisited) {
currNode.leftVisited = true;
stack.push(currNode.leftNode);
} else if (currNode.rightNode != null && !currNode.rightVisited) {
System.out.print(currNode.i);
currNode.rightVisited = true;
stack.push(currNode.rightNode);
} else {
System.out.print(currNode.i);
stack.pop();
}
} else {
stack.pop();
}
}

}

private static void dfsStackPstOrder(Node root) {
final Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
final Node currNode = stack.peek();
if (!currNode.leftVisited || !currNode.rightVisited) {
if (currNode.leftNode != null && !currNode.leftVisited) {
currNode.leftVisited = true;
stack.push(currNode.leftNode);
} else if (currNode.rightNode != null && !currNode.rightVisited) {
currNode.rightVisited = true;
stack.push(currNode.rightNode);
} else {
System.out.print(currNode.i);
stack.pop();
}
} else {
System.out.print(currNode.i);
stack.pop();
}
}

}
}

class Node {
Node(int i) {
this.i = i;
}

int i;
boolean leftVisited = false;
boolean rightVisited = false;
Node leftNode;
Node rightNode;
}