Depth First Search in C++. To compile: g++ -std=c++11 dfs.cpp

dfs.cpp

//Title: Depth first search in C++
//Author: Shaun Cheng
//Date: 1/18/2016
#include <iostream>
#include <array>
#include <vector>
#include <string>
#include <stack>
using namespace std;

//////////////////////////////////////////////////////////
//This is an iterative DFS implementation using stack on heap memory.
//The children of each node is an iterable container, else it won't compile.
//Parameters:
//1)pass node, the root of the tree
//2)pass a predicate that has a function: bool operator().
//Returns:
//the node which passes the predicate, or, nullptr if such node cannot be found.
//Time Complexity:
//O(N) where N is num of nodes.
//Space Complexity:
//O(N) where N is num of nodes. 
//Note: a recursive implementation could run faster and use less memory.
//However, since we are not given a balanced tree, a recursive solution 
//runs the risk of stack overflow for high trees.
//Hence an iterative implementation is chosen here.
//////////////////////////////////////////////////////////
    template <class T, class UnaryPredicate>
T* dfs(T *node, UnaryPredicate pred)
{
    stack<T*> dfs_stack;
    if(node) dfs_stack.push(node);
    while(!dfs_stack.empty()) {
        T *top = dfs_stack.top();
        dfs_stack.pop();
        if(pred(*top)) return top;
        for(auto n:top->children)
            if(n) dfs_stack.push(n);
    }
    return nullptr;
}

//////////////////////////////////////////////////////////
//NOTE: The following code is to test the above function works.
//For the code to compile, a node much have public members: 
//name: a string denoteing name of the node
//children: a container(w/ iterator interface) for its child nodes; 
//////////////////////////////////////////////////////////

//prints tree in human readable format
    template <class T>
void print_tree(T *node, int offset=0)
{
    if(node == nullptr) return;
    for(int i=0; i<offset; ++i) cout <<"|_";
    cout <<node->name<<endl;
    ++offset;
    for(auto n:node->children) print_tree(n, offset);
}

//test dfs with general K-ary tree
//name is string
//children container is vector
void test_K_ary_tree(const string &search_key)
{
    struct TreeNode {
        TreeNode(){}
        TreeNode(const string &s):name(s){}
        string name;
        vector<TreeNode*> children;
    };
    TreeNode a("a");
    TreeNode b("b");
    TreeNode c("c");
    TreeNode d("d");
    TreeNode e("e");
    TreeNode f("f");
    TreeNode g("g");
    TreeNode h("h");

    a.children.push_back(&b);
    a.children.push_back(&c);
    b.children.push_back(&d);
    b.children.push_back(&e);
    b.children.push_back(&f);
    c.children.push_back(&g);
    g.children.push_back(&h);

    cout <<"Printing the K-ary tree:"<<endl;
    print_tree(&a);
    auto pred = [&search_key](const TreeNode &node) {
        return 0 == node.name.compare(search_key);
    };
    cout <<"\nThe search result using dfs for name '"<<search_key<<"' is:\n";
    print_tree(dfs(&a, pred));
}

//test dfs with a binary tree
//name is integer
//children container is c++11 array
void test_binary_tree(int search_key)
{
    struct Node{
        Node(){}
        Node(int i):name(i){}
        int name;
        array<Node*, 2> children = {{nullptr, nullptr}};
    };
    Node a(1);
    Node b(2);
    Node c(3);
    Node d(4);
    Node e(5);
    Node f(6);
    Node g(7);
    Node h(8);
    a.children[0] = &b;
    a.children[1] = &c;
    b.children[0] = &d;
    b.children[1] = &e;
    c.children[0] = &g;
    c.children[1] = &h;

    cout <<"Printing the binary tree:"<<endl;
    print_tree(&a);
    auto pred = [search_key](const Node &node) {
        return node.name == search_key;
    };
    cout <<"\nThe search result using dfs for name '"<<search_key<<"' is:\n";
    print_tree(dfs(&a, pred));
}

//main function to test *-first search
int main()
{
    cout <<">>>>>>>>>>>>>>>>>>>TESTING K-ARY TREE<<<<<<<<<<<<<<<<<<<<<<<<<<" << endl;
    test_K_ary_tree("g");
    cout <<">>>>>>>>>>>>>>>>>>>TESTING BINARY TREE<<<<<<<<<<<<<<<<<<<<<<<<<<" << endl;
    test_binary_tree(2);
}