byte sized c++

Queue

17.7 - Breadth-first search

Breadth-first search is an algorithm to traverse or search a tree. Starting at the tree root, it traverses all the nodes at the current level before moving onto the next one. This is the opposite to depth-first search, which traverses all the way to the deepest node on a branch before moving onto the next one.

Your task is to implement the breadth_first_search function which accepts a root node and prints each element by breadth-first order.

Sample input code

int main()
{
    auto a = new Node<char>('a');
    auto b = new Node<char>('b');
    auto c = new Node<char>('c');
    auto d = new Node<char>('d');
    auto e = new Node<char>('e');
    auto f = new Node<char>('f');
    auto g = new Node<char>('g');
    auto h = new Node<char>('h');
    auto i = new Node<char>('i');
    auto j = new Node<char>('j');

    a->children = {b, c, d};
    b->children = {e};
    c->children = {f};
    d->children = {i};
    e->children = {g, h};
    i->children = {j};

    breadth_first_search<char>(a);
}

Sample output

a
b
c
d
e
f
i
g
h
j