Breadth-First Search Traversal (Trees)

BFS Explained

Breadth-First Search (BFS) is a method for exploring trees in a systematic way. Think of it as if you’re searching a tree level by level, starting from the top. You first look at the nodes closest to the root, then move on to nodes one level deeper, and so on.

BFS is like ripples expanding in a pond after you drop a pebble. You check all the nodes at a particular level before moving down to the next level. This helps you find things quickly, especially when you want to find something closer to the top before going deeper.

When you’re dealing with trees, BFS can help you understand the tree’s shape and how things are connected on the same level. It’s a handy tool if you’re trying to figure out the basic structure of a tree.

Each level of the tree using BFS is searched first before traversing to the next level. It looks like this:

Let’s say we want to traverse a tree using BFS, and store each of the TreeNode’s data in an array once it has been traversed. The end result of the following tree would look like:

To Begin

A TreeNode is a basic building block in a tree data structure. It represents a single element or node within the tree. Each TreeNode has a value (or data) and can have references to its child nodes. In a typical binary tree, for example, each TreeNode can have up to two child nodes, often referred to as the left child and the right child. These child nodes can themselves be TreeNodes, forming a hierarchical structure. Overall, a TreeNode holds information and connections that define how elements are organized within a tree.

Lets first implement a TreeNode class in Java, and a main method that sets up the tree pictured above.

public static class TreeNode {
    private int data;
    private TreeNode left;
    private TreeNode right;
    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public static void main(String[] args) {
    TreeNode nine = new TreeNode(9);
    TreeNode four = new TreeNode(4);
    TreeNode twenty = new TreeNode(20);
    TreeNode one = new TreeNode(1);
    TreeNode six = new TreeNode(6);
    TreeNode fifteen = new TreeNode(15);
    TreeNode thirty = new TreeNode(30);

    nine.left = four;
    nine.right = twenty;
    four.left = one;
    four.right = six;
    twenty.left = fifteen;
    twenty.right = thirty;
}

Breadth-First Search

Breadth-first search utilizes a queue data structure. A queue is an ideal data structure for this purpose because it maintains the FIFO ordering. When you start BFS from the source node, you enqueue its children (all nodes at distance 1 from the source). Then, as you dequeue each node, you enqueue their neighbors (nodes at distance 2), and so on. This guarantees that nodes at the same level are visited before going deeper.

Let’s first take a look at the solution:

public static ArrayList<Integer> bfs(TreeNode root) {
    TreeNode cur = root;
    ArrayList<Integer> result = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(cur);
    while(!queue.isEmpty()) {
        cur = queue.remove();
        result.add(cur.data);
        if(cur.left != null) {
            queue.add(cur.left);
        }
        if(cur.right != null) {
            queue.add(cur.right);
        }
    }
    return result;
}

Here, we first implement both a list (which will hold our result), and a queue.

• Note: The LinkedList class in Java implements the Queue interface, which means you can use it as a queue to perform BFS.

We begin by adding the root of the tree to the queue, and then beginning a while loop that runs while the queue contains TreeNodes.

Within this loop, we take the first TreeNode in the queue, add its data to our result array, and then add the TreeNode's children into the queue. Let’s walk step by step through our example:

Example

We begin with the queue being populated with the root value, 9. The result is currently empty

The first value of queue , 9 is dequeued, and is added to result. The left and right children of 9 are added to the queue , which are 4 & 20.

The first value of queue , 4 is dequeued, and is added to result. The left and right children of 4 are added to the queue , which are 1 & 6.

The first value of queue , 20 is dequeued, and is added to result. The left and right children of 4 are added to the queue , which are 15 & 30.

The TreeNodes with values 1, 6, 15, & 30 do not have any children. They are simply taken from the queue (starting at the beginning) each time and placed in the result.

We are left with a result array that accurately that is breadth-first searched.

Entire Solution

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstSearch {

    public static ArrayList<Integer> bfs(TreeNode root) {
        TreeNode cur = root;
        ArrayList<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(cur);
        while(!queue.isEmpty()) {
            cur = queue.remove();
            result.add(cur.data);
            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }
        }
        return result;
    }


    public static class TreeNode {
        private int data;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    public static void main(String[] args) {
        TreeNode nine = new TreeNode(9);
        TreeNode four = new TreeNode(4);
        TreeNode twenty = new TreeNode(20);
        TreeNode one = new TreeNode(1);
        TreeNode six = new TreeNode(6);
        TreeNode fifteen = new TreeNode(15);
        TreeNode thirty = new TreeNode(30);

        nine.left = four;
        nine.right = twenty;
        four.left = one;
        four.right = six;
        twenty.left = fifteen;
        twenty.right = thirty;

        ArrayList<Integer> bfs = bfs(nine);
    }
}

Performance Analysis

Time Complexity

• The time complexity of BFS on a tree is O(N), where N is the number of nodes in the tree. In a tree, each node is visited exactly once, and every edge is traversed once, as there’s only one path between any two nodes. This linear time complexity ensures efficient exploration of the entire tree.

Space Complexity

• The space complexity of BFS on a tree is O(W), where W is the maximum width (number of nodes in the widest level) of the tree. In the worst case, the queue used for BFS holds all nodes at the widest level, which is the maximum number of nodes present in a single level of the tree.
• In the case above, the maximum width of the tree was 4, and we saw that at most, the queue held 4 integers [ 1, 6, 15, 30 ]