# Trying to implement BFS and I am stuck

I am trying to write down a code which would blindly search for a condition using breadth first search.I have been thinking of it for quite some time and I cant figure out how to continue.

On the one hand the data structure is a tree with each node having n children so in order to tranverse every node of the tree you need recursion

On the other hand though in recursive algorithms the return value is each time for a path from root to a leaf and we dont want this, we want breadth first search ,we want to access in 2 nodes of the same level in the tree before we keep on checking the rest of the tree so I am in a endless loop as you can see.

The pseudo code for DFS using recursion would look something like this:

def DFS(node):
if node is visited:
return
mark node as visited
for each child in node:
DFS(child)


This recursive method works because every time we call the function it goes as deep as it can into the tree before returning. When it returns, it goes to the next child and repeats the process. This ensures that we are going as deep as possible, exploring one branch fully before moving on to the next one.

If you want to avoid recursion, you can also implement DFS using a stack data structure. For example:

public void dfsWithoutRecursion(Node root) {
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node current = stack.pop();
System.out.println(current.value);
for (Node child : current.children) {
stack.push(child);
}
}
}



Here we start by pushing the root node onto the stack. Then we enter a loop that continues as long as the stack is not empty. Inside the loop we pop the top node from the stack and print its value. Then we push all of its children onto the stack. This process continues until the stack is empty which means we've visited every node in the tree.

You mentioned that you wish to implement BFS instead of DFS. The code for BFS can be very similar, simply replace the Stack above with a Queue.