Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
Select your favorite languages :
  • Or search :

Idiom #128 Breadth-first traversing of a tree

Call a function f on every node of a tree, in breadth-first prefix order

A tree with 6 nodes, rooted at node 1 
#include <deque>
#include <functional>
void bfs(Node& root, std::function<void(Node*)> f) {
  std::deque<Node*> node_queue;
  node_queue.push_back(&root);
  while (!node_queue.empty()) {
    Node* const node = node_queue.front();
    node_queue.pop_front();
    f(node);
    for (Node* const child : node->children) {
      node_queue.push_back(child);
    }
  }
}
func (root *Tree) Bfs(f func(*Tree)) {
	if root == nil {
		return
	}
	queue := []*Tree{root}
	for len(queue) > 0 {
		t := queue[0]
		queue = queue[1:]
		f(t)
		queue = append(queue, t.Children...)
	}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Consumer;
static void breadthFirstSearch(Node root, Consumer<Node> f) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    while(!queue.isEmpty()) {
        Node polled = queue.poll();
        f.accept(polled);
        polled.children.forEach(a -> queue.offer(a));
    }
}
     
def BFS(f, root):
	Q = [root]
	while Q:
		n = Q.pop(0)
		f(n)
		for child in n:
			if not n.discovered:
				n.discovered = True
				Q.append(n)
use std::collections::VecDeque;
struct Tree<V> {
    children: Vec<Tree<V>>,
    value: V
}

impl<V> Tree<V> {
    fn bfs(&self, f: impl Fn(&V)) {
        let mut q = VecDeque::new();
        q.push_back(self);

        while let Some(t) = q.pop_front() {
            (f)(&t.value);
            for child in &t.children {
                q.push_back(child);
            }
        }
    }
}
New implementation...
programming-idioms.org 
void bfs(Node& root, std::function<void(Node*)> f) {
  std::deque<Node*> node_queue;
  node_queue.push_back(&root);
  while (!node_queue.empty()) {
    Node* const node = node_queue.front();
    node_queue.pop_front();
    f(node);
    for (Node* const child : node->children) {
      node_queue.push_back(child);
    }
  }
}
func (root *Tree) Bfs(f func(*Tree)) {
	if root == nil {
		return
	}
	queue := []*Tree{root}
	for len(queue) > 0 {
		t := queue[0]
		queue = queue[1:]
		f(t)
		queue = append(queue, t.Children...)
	}
}
static void breadthFirstSearch(Node root, Consumer<Node> f) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    while(!queue.isEmpty()) {
        Node polled = queue.poll();
        f.accept(polled);
        polled.children.forEach(a -> queue.offer(a));
    }
}
     
def BFS(f, root):
	Q = [root]
	while Q:
		n = Q.pop(0)
		f(n)
		for child in n:
			if not n.discovered:
				n.discovered = True
				Q.append(n)
struct Tree<V> {
    children: Vec<Tree<V>>,
    value: V
}

impl<V> Tree<V> {
    fn bfs(&self, f: impl Fn(&V)) {
        let mut q = VecDeque::new();
        q.push_back(self);

        while let Some(t) = q.pop_front() {
            (f)(&t.value);
            for child in &t.children {
                q.push_back(child);
            }
        }
    }
}