Breath-First Search using Stack

· 4 min read

1. BFS using Queue

Just in the prior post on graph traversal, we went into details of Depth-First Search (DFS) and Breadth-First Search (BFS). BFS is a way of traversing down the graph, level-by-level. Specifically for a balanced-tree, the first/root node is visited first, followed by its immediate children, then followed by the next level children, and so on. Here's the same example of BFS using a queue:

2. Problem: Space Complexity

The problem with this solution is adding all the immediate children to the queue before visiting them. While this isn't much of a concern for a binary tree, imagine a non-binary tree where at each level the number of nodes grows exponentially. In the example below, when the second-level node G is visited, the queue now has 49 entries. For the nth level: 7^(N-1) nodes. For level 100, there would be 282,475,249 entries in the queue. Nearly 300 million entries and a 4-byte address pointer per entry would lead to around ~1 MB.

3. Solution: BFS using Stack

The recursive approach below, the space coordinate depends on the number of levels. In a balanced tree, the space complexity is now O(log(n)), where n is the total number of nodes.

Pusedo Code:

procedure bfs(root:NODE*);
    var target = 0;
    var node = root;
BEGIN
    for each level in tree do
    begin
        printtree(node, target, 0);
        target = target + 1;
    end
END

procedure printtree(node:NODE*, target:int, level:int);
BEGIN
    if(target > level) then
    begin
        for each child of node do
            printtree(child, target, level + 1);
    end
    else
        print node;
END

Going back to the same example for a balanced binary tree with nodes: A, B, C, D, E, F, G

Initializing the root node and setting the initial target level to 0. The main BFS loop iterates through each level of the tree, incrementing the target level after processing each one.

Iteration 1 (target = 0)

Step Action Current Call Stack Visited Nodes
1 Initial setup
2 Iteration with target=0 printtree(A, 0, 0)
3 Visiting A A

For each level, the printtree function is called with the current node, the target level, and the current level (starting from zero). Checks if the target level is greater than the current level. If so, recursively call for each child of the current node, incrementing the level by 1. This continues until the target level equals the current level, at which point the node is printed.

Iteration 2 (target = 1)

Step Action Current Call Stack Visited Nodes
4 target=1 A
5 Iteration with target=1 printtree(A, 1, 0) A
6 Call B printtree(A, 1, 0) → printtree(B, 1, 1) A
7 Visiting B printtree(A, 1, 0) A, B
8 Call C printtree(A, 1, 0) → printtree(C, 1, 1) A, B
9 Visiting C printtree(A, 1, 0) A, B, C

by incrementing the target level and repeating the process until all levels of the tree have been processed, nodes are printed level-by-level, leadind to a breadth-first traversal.

Iteration 3 (target = 2)

Step Action Current Call Stack Visited Nodes
10 target=2 A, B, C
11 Iteration with target=2 printtree(A, 2, 0) A, B, C
12 Call B printtree(A, 2, 0) → printtree(B, 2, 1) A, B, C
13 Call D printtree(A, 2, 0) → printtree(B, 2, 1) → printtree(D, 2, 2) A, B, C
14 Visiting D printtree(A, 2, 0) → printtree(B, 2, 1) A, B, C, D
15 Call E printtree(A, 2, 0) → printtree(B, 2, 1) → printtree(E, 2, 2) A, B, C, D
16 Visiting E printtree(A, 2, 0) → printtree(B, 2, 1) A, B, C, D, E
17 Call C printtree(A, 2, 0) → printtree(C, 2, 1) A, B, C, D, E
18 Call F printtree(A, 2, 0) → printtree(C, 2, 1) → printtree(F, 2, 2) A, B, C, D, E
19 Visiting F printtree(A, 2, 0) → printtree(C, 2, 1) A, B, C, D, E, F

4. Recursive BFS: Implementation

Without much explanation, here's an implementation in Java. In the Node class, children is an array of `Node`s, but it also works with other data structures, such as a LinkedList.

class Node {
    char data;
    Node[] children;

    Node(char data, int childCount) {
        this.data = data;
        this.children = new Node[childCount];
    }
}

public class TreeTraversal {

    // BFS subroutine
    boolean printTree(Node node, int target, int level) {
        boolean returnValue = false;
        if (target > level) {
            for (int i = 0; i < node.children.length; i++) {
                if (printTree(node.children[i], target, level + 1)) {
                    returnValue = true;
                }
            }
        } else {
            System.out.print(node.data);
            if (node.children.length > 0) {
                returnValue = true;
            }
        }
        return returnValue;
    }

    // BFS routine
    void printBfsTree(Node root) {
        if (root == null) return;
        int target = 0;
        while (printTree(root, target++, 0)) {
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Node root = new Node('A', 2);
        root.children[0] = new Node('B', 2);
        root.children[1] = new Node('C', 1);
        root.children[0].children[0] = new Node('D', 0);
        root.children[0].children[1] = new Node('E', 0);
        root.children[1].children[0] = new Node('F', 0);

        TreeTraversal treeTraversal = new TreeTraversal();
        treeTraversal.printBfsTree(root);
    }
}

5. Conclusion

The prime difference between the queue-based BFS and stack-based BFS is that the space coordinate of queue-based BFS depends on the number of children and for stack-based BFS, it's the depth/height of the tree.

Taking an example, say we have a balanced tree with 9 levels (root node being level 1) and each node has 10 children. In the queue-based BFS solution, the number of nodes in the queue at level 9 would be C^(N - 1), where N is the number of levels and C is the number of children per node. For C = 10 and N = 9, this results in 10^(9 - 1) = 10^8. Presuming each node is 4 bytes, that's 400 MB in the queue (at level 9).

The stack-based solution, on the other hand, the call-stack can have at most L (number of levels) recursive calls (one for each child), but only one call at a time will be active in the stack for each depth level. Realistically the stack contains other data such as return address, local variables, saved registers, etc., and taking each stack frame size of 64 bytes, the space of the callstack at most is 9 × 64 bytes = 576 bytes.

This is considerable space saving! At much higher levels, say 50 levels, the stack-based solution outperforms queue-based BFS in both time and space coordinates. However, for a more irregular/high-depth tree, queue-based BFS performs better.

6. References

[1] Pravin Kumar Sinha, "Stack-based breadth-first search tree traversal," IBM Developer. [Online]. Available: https://developer.ibm.com/articles/au-aix-stack-tree-traversal.
[2] Wikipedia contributors, "Breadth-first search," Wikipedia, The Free Encyclopedia. [Online]. Available: https://en.wikipedia.org/wiki/Breadth-first_search.
[3] Adesh Nalpet Adimurthy, "Graph Theory: Search and Traversal," PyBlog, 2024. [Online]. Available: https://www.pyblog.xyz/graph-traversal.

Cite this article as: Adesh Nalpet Adimurthy. (Jul 21, 2024). Breath-First Search using Stack. PyBlog. https://www.pyblog.xyz/stack-based-bfs

#index table of contents