[Algorithms] 6 - My Solution for PrintTree Problem (DFS)

 #include <iostream> #include <vector> #include <string> #include <utility> // std::pair, std::make_pair #include <unordered_map>  using namespace std; void DFS(int depth, string key, unordered_map<string, vector<string>> mp){ if(!mp.count(key))// if key does not exist return; vector<string> values = mp[key]; for (int i = 0; i < values.size(); i++){ for (int j = 0; j < depth; j++) cout << "\t"; cout << values[i] << endl; DFS(depth+1, values[i], mp); } } int main() { vector<pair<string, string>> input; input.push_back(make_pair("animal", "mammal")); input.push_back(make_pair("animal", "bird")); input.push_back(make_pair("lifeform", "animal")); input.push_back(make_pair("cat", "lion")); input.push_back(make_pair("mammal", "cat")); input.push_back(make_pair("animal", "fish")); unordered_map<string, vector<string>> mp; unordered_map<string, bool> seen; for (auto p : input){ string key = p.first; string val = p.second; seen[val] = true; if(mp.count(key)){ mp[key].push_back(val); } else { vector<string> arr = {val}; mp[key] = arr; } } // Finding the start point (root node) // 1. Brute force: Use DFS and count the height // 2. If the string ever appeared in the p.second (as a val) then remove from the candidate string root = ""; for (auto m : mp){ if(!seen.count(m.first)){ root = m.first; } } cout << root << endl; DFS(1, root, mp); // Use DFS to print out every child // Need to add depth for every vector array return 0; }