Logo

Programming-Idioms

  • C++
  • Ruby

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

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.

New implementation...