Logo

Programming-Idioms

# 128 Breadth-first traversing of a tree
Call a function f on every node of a tree, in breadth-first prefix order
New implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations 
#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));
    }
}
     
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);
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)
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

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

Preview