byte sized c++

Stack

16.7 - Depth-first search

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

Your task is to implement the depth_first_search function which accepts a root node and prints each element by depth-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};

    depth_first_search<char>(a);
}

Sample output

a
b
e
g
h
c
f
d
i
j