Logo

Programming-Idioms

  • Python
  • Go

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 
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...)
	}
}

Bfs is a method of type *Tree, and takes function f as an argument.

The queue grows and shrinks during traversal, until all nodes have been visited.
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)
#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);
    }
  }
}
New implementation...
< > ⌨
programming-idioms.org 
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...)
	}
}
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)
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);
    }
  }
}
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));
    }
}
     
sub bft {
    my ($f, $node) = @_;
    my @children = $node->getAllChildren;
    return unless @children;
    foreach my $child ( @children ) {
        $f->( $child->getNodeValue );
    }   
    foreach my $child ( @children ) {
        bft($f, $child);
    }
}

my $f = sub { print $_[0], "\n" };

# create a tree and populate it, then call bft()
bft($f, $tree);
class Tree
  attr_accessor :value, :children

  def initialize(value)
    @value = value
    @children = []
  end

  def traverse_breadth_first(f)
    queue = []
    queue.unshift(self)
    while !(queue.empty?)
      node = queue.pop
      method(f).call(node.value)
      node.children.each { |child| queue.unshift(child) }
    end
  end
end

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);
            }
        }
    }
}