## the approach

Now back to the data structure, for such a data structure, BFS needs use a Queue for tracking visited nodes and what adjacent nodes to check next in a breadth-first way of visiting. The order of the nodes in the queue is the order to check for their unvisited adjacent children. On the other hand, a DFS needs a Stack for tracking just-visited nodes and what adjacent nodes to check next in a depth-first way of traversing.

## thought process

**Breadth First Search (BFS)**

A Queue has FIFO (first-in-first-out) nature. In Java, use LinkedList class for queue.

Start from the root node, enqueue it as the first step. In general, you want to enqueue just-visited children nodes in a breadth first algorithm. For each node in the queue, all the children nodes of a node will be checked for their unvisited adjacent nodes to be enqueued and then mark visited. Only unvisited node should be visited, enqueued, then be marked as visited immediately after being enqueued. En-queuing node is a way to say that the node has just been visited in a BFS approach, the children of each node in the queue will be checked for its children. No node will be enqueued more than once because no node will be visited twice.

To find the next node to traverse, dequeue to get a visited node to search for all its adjacent unvisited candidates. Dequeue a node means none of its child worth being checked for unvisited nodes any more. Once found such unvisited child nodes, enqueue them then and make them visited, so these just visited nodes will be checked for their unvisited adjacent nodes later. The process goes on until nothing left in the queue.

**Depth First Search (DFS)**

A Stack has FILO (first-in-last-out) nature. In Java, use Stack class for Stack.

Start from the root node, push it into the Stack. For nodes in the Stack, each of node's unvisited children nodes will be traversed eventually. In general, you want to push only 'one' child of a just-visited node so that child node will be checked for its one unvisited adjacent node to go deeper into the tree. Pushing a node means the node has just been visited. When checking for unvisited child nodes, 'peek' the Stack for a just-visited candidate to search for its unvisited child nodes. Only 'pop' when a just-visited node has absolutely no more unvisited child to go deeper into the tree traversal.

## code walk-through

public static class Node{

private int value;

private ArrayList<Node> child_nodes = new ArrayList<Node>();

public boolean visited = false;

public Node(int value){

this.value = value;

}

public String toString(){

return Integer.toString(value);

}

public ArrayList<Node> getAllChildNodes(){

return child_nodes;

}

public Node getOneUnvisitedChildNode(){

for(Node n: child_nodes){

if (n.visited == false){

return n;

}

}

return null;

}

public ArrayList<Node> getUnvisitedChildNodes(){

ArrayList<Node> unvisited_nodes= new ArrayList<Node>();

for(Node n: child_nodes){

if (n.visited == false){

unvisited_nodes.add(n);

}

}

return unvisited_nodes;

};

public Node addChild(Node n){

child_nodes.add(n);

return Node.this;

}

}

public static class TraverseStrategy{

public static void markTreeUnvisited(Node n){

n.visited = false;

for(Node c: n.getAllChildNodes()){

markTreeUnvisited(c);

}

}

}

public static class BFSStrategy extends TraverseStrategy{

public static void search(Node n){

markTreeUnvisited(n); // mark all nodes unvisited

LinkedList queue = new LinkedList<Node>();

queue.add(n);

System.out.println(n);

while(!queue.isEmpty()){

Node node = (Node) queue.remove();

for(Node c:node.getUnvisitedChildNodes()){

queue.add(c); // enqueue

System.out.println(c); // visit the node

c.visited = true; // immediately mark visited

}

}

}

}

public static class DFSStrategy extends TraverseStrategy{

public static void search(Node n){

markTreeUnvisited(n); // mark all nodes unvisited

Stack stack = new Stack<Node>();

stack.push(n);

System.out.println(n);

while(!stack.isEmpty()){

Node node = (Node) stack.peek();

Node unvisited_child_node = node.getOneUnvisitedChildNode();

if (unvisited_child_node != null){

stack.push(unvisited_child_node); // push

System.out.println(unvisited_child_node); // visit the node

unvisited_child_node.visited = true; // immediately mark visited

}

else{

stack.pop();

}

}

}

}

public static void main (String[] args) throws java.lang.Exception

{

// initialize the tree
Output:
BFS: 1 2 3 4 6 5 |