byte sized c++

Recursion

19.4 - Recursive depth-first search

Depth-first search can be implemented recursively, because it relies on the function call stack. Depth-first search traverses from the root node and explores as deep as possible before backtracking.

Your task is to implement the function called depth_first_search which accepts a root node then prints the content of the tree by traversing it in a 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