Vertical Order traversal of a tree from the bottom

#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;
}

Leave a comment