0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Sorry delete your answer I made a typo. $\endgroup$ Nov 23, 2023 at 23:48
  • $\begingroup$ The question is for BFS, not DFS. The code for BFS can be very similar, by the way. $\endgroup$ Nov 25, 2023 at 20:19
  • $\begingroup$ I think he changed the question and edited it! @reinierpost $\endgroup$ Nov 26, 2023 at 9:39
  • $\begingroup$ Well, change the Stack to a Queue ... $\endgroup$ Nov 27, 2023 at 11:59
0
$\begingroup$

Every tree is also a graph. Therefore, you can use breadth-first search directly on a tree. It doesn't require recursion; you can use a queue and a loop. As soon as you encounter a node that satisfies the condition, you stop and return immediately, without continuing the search.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.