#include <iostream> #include <vector> #include <memory> #include <map> using namespace std; typedef map<int, vector<int>> Map; class Tree { class TreeNode { public: unique_ptr<TreeNode> left, right; int el; explicit TreeNode(int _el) : el{_el} {} TreeNode() = default; ~TreeNode() = default; TreeNode(TreeNode &&) = default; TreeNode& operator=(TreeNode &&) = default; TreeNode(TreeNode const& ) = delete; TreeNode& operator=(TreeNode const&) = delete; /* Populates Map in vertical order */ void verticalOrder(Map &m, int distance) const { m[distance].push_back(el); if (left != nullptr) { left->verticalOrder(m, distance - 1); } if (right != nullptr) { right->verticalOrder(m, distance + 1); } } }; unique_ptr<TreeNode> root; /* Example Tree: 1 / \ 2 3 / \ / \ 4 5 6 7 \ \ 8 9 */ public: Tree() { root = unique_ptr<TreeNode>{new TreeNode{1}}; root->left = unique_ptr<TreeNode>{new TreeNode{2}}; root->right = unique_ptr<TreeNode>{new TreeNode{3}}; root->left->left = unique_ptr<TreeNode>{new TreeNode{4}}; root->left->right = unique_ptr<TreeNode>{new TreeNode{5}}; root->right->left = unique_ptr<TreeNode>{new TreeNode{6}}; root->right->right = unique_ptr<TreeNode>{new TreeNode{7}}; root->right->left->right = unique_ptr<TreeNode>{new TreeNode{8}}; root->right->right->right = unique_ptr<TreeNode>{new TreeNode{9}}; } Map verticalOrder() { Map m; if (root != nullptr) { root->verticalOrder(m, 0); } return m; } }; int main(int argc, char const *argv[]) { Tree t; Map m {t.verticalOrder()}; for (auto& p : m) { for (auto el : p.second) { cout << el << " "; } cout << endl; } return 0; }