main.cpp

#include <iostream>
#include "tree.h"

int main(){
    /* Create the tree as illustrated in thr
    * program challenge description.
    */

    Tree *tree = new Tree('a');
    Node *temp_b = tree->create_child(tree->root, 'b');
    Node *temp_c = tree->create_child(tree->root, 'c');
    Node *temp_d = tree->create_child(temp_b, 'd');
    Node *temp_e = tree->create_child(temp_b, 'e');
    Node *temp_f = tree->create_child(temp_b, 'f');
    Node *temp_g = tree->create_child(temp_c, 'g');
    Node *temp_h = tree->create_child(temp_g, 'h');

    tree->insert_node(tree->root, temp_b);
    tree->insert_node(tree->root, temp_c);
    tree->insert_node(temp_b, temp_d);
    tree->insert_node(temp_b, temp_e);
    tree->insert_node(temp_b, temp_f);
    tree->insert_node(temp_c, temp_g);
    tree->insert_node(temp_g, temp_h);

    std::cout << "Tree size is: " << tree->size << std::endl;
    std::cout << "The root of the tree is: " << static_cast<char> (tree->root->element) << std::endl;

    bool exists;
    Node *result;

    std::tie(exists, result) = tree->search(tree->root, static_cast<int> ('z'));
    if (exists == true) {
        std::cout << "Found! " << static_cast<char> (result->element) << std::endl;
    }
    else if (exists == false) {
        std::cout << "False, the requested node does not exist." << std::endl;
    }
    return 0;
}

tree.cpp

#include "tree.h"
#include <iostream>
#include <queue>

Tree::Tree(int value) {
    this->root = new Node;
    this->root->element = value;
    this->root->parent = NULL;
    size+= 1;
}
Tree::~Tree() {
    delete root;
}

bool Tree::is_leaf(Node *node) {
    if (node->children.empty()) {
        return true;
    }
    return false;
}
void Tree::insert_node(Node *parent, Node *child) {
    //Node *temp = create_child(parent, item);
    parent->children.push_back(child);
    size += 1;
}

Node  *Tree::create_child(Node *parent, int item) {
    Node *child = new Node;
    child->element = item;
    child->parent = parent;
    return child;
}

Node *Tree::depth_first_search(Node *root, int item) {
    if (root->element == item) {
        return root;
    }
    auto children = root->children.size();
    for (std::vector<Node *>::size_type i = 0; i != children; i++) {
        std::cout << "Going through " << static_cast<char> (root->children[i]->element) << std::endl;
        Node *found =  depth_first_search(root->children[i], item);
        if (found != nullptr) {
                return found;
        }
    }
    return NULL;
}

std::tuple<bool, Node *> Tree::search(Node *start, int item) {
    std::tuple<bool, Node *> result;
    Node *found = depth_first_search(start, item);
    if (found) {
        result = std::make_tuple(true, found);
        return result;
    }
    result = std::make_tuple(false, nullptr);
    return result;
}

tree.h

#ifndef TREE_H
#define TREE_H
#include <vector>
#include <list>
#include <tuple>

struct Node {
    // This is a node in the tree.
    int element;
    Node *parent;
    std::vector<Node *> children;
};

class Tree {
    public:
        Tree(int);
        ~Tree();
        Node *root;
        int size;
        std::tuple<bool, Node *> search(Node *, int);
        bool is_leaf(Node *);
        void insert_node(Node *, Node *);
        Node *create_child(Node *, int);
    private:
        void add_children(Node *, int);
        Node *depth_first_search(Node *, int);        
};
#endif