Binary Tree BFS (Breadth-First Search)
Tree Selection
Playback Controls
Tree Selection
Leave empty to see full BFS traversal, or enter a number to search for it
Playback Controls
Algorithm Progress
Algorithm Progress
Reference implementation of BFS (Breadth-First Search). Select a language tab to view and copy the code.
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
void bfs(int graph[MAX][MAX], int n, int start) {
bool visited[MAX] = {false};
int queue[MAX], front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start;
while (front < rear) {
int node = queue[front++];
printf("%d ", node);
for (int i = 0; i < n; i++) {
if (graph[node][i] && !visited[i]) {
visited[i] = true;
queue[rear++] = i;
}
}
}
}#include <vector>
#include <queue>
void bfs(const std::vector<std::vector<int>>& adj, int start) {
int n = static_cast<int>(adj.size());
std::vector<bool> visited(n, false);
std::queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front(); q.pop();
// process node
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}import java.util.*;
public static void bfs(List<List<Integer>> adj, int start) {
int n = adj.size();
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
// process node
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}from collections import deque
def bfs(adj: list[list[int]], start: int) -> list[int]:
visited = [False] * len(adj)
order = []
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
order.append(node)
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return orderfunction bfs(adj, start) {
const visited = new Array(adj.length).fill(false);
const order = [];
const queue = [start];
visited[start] = true;
while (queue.length) {
const node = queue.shift();
order.push(node);
for (const neighbor of adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
return order;
}Python — Code Walkthrough
collections.deque for O(1) popleft
from collections import deque; queue = deque([start])A Python list used as a queue has O(n) pop(0). collections.deque provides O(1) popleft and append, making it the standard choice for BFS in Python.
Initialise with start node already marked
queue = deque([start]); visited[start] = TrueMarking the start node before the loop follows the same "mark when enqueued" pattern, ensuring correctness even if the graph has a self-loop at the start node.
node = queue.popleft()
node = queue.popleft()popleft removes from the left (front) of the deque — the FIFO behavior needed for BFS. queue.pop() would give LIFO (DFS) behavior.
Returns traversal order
return orderRather than side-effecting with print, the function collects nodes into a list and returns it — more Pythonic and easier to test.