Return to Revisions

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.