fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Print Binary Tree Vertically
  4. //
  5. //  Created by Himanshu on 25/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  12.  
  13. struct node {
  14.     int value = 0;
  15.     struct node *left, *right;
  16. };
  17. typedef struct node Node;
  18.  
  19. node* newNode(int data)
  20. {
  21.     node* Node = new node();
  22.     Node->value = data;
  23.     Node->left = NULL;
  24.     Node->right = NULL;
  25.  
  26.     return(Node);
  27. }
  28.  
  29. void printVertically (Node *root) {
  30.     if (root == NULL) {
  31.         return;
  32.     }
  33.  
  34.     map<int, vector<int>> hmap;
  35.     map<int, vector<int>>::iterator it;
  36.     queue<pair<Node*, int>> qu;
  37.     int level = 0;
  38.  
  39.     qu.push(make_pair(root, level));
  40.  
  41.     while (!qu.empty()) {
  42.         int size = (int) qu.size();
  43.         for (int i=0; i<size; i++) {
  44.             pair<Node*, int> node = qu.front();
  45.             qu.pop();
  46.             Node *temp = node.first;
  47.             level = node.second;
  48.  
  49.             hmap[level].push_back(temp->value);
  50.  
  51.             if (temp->left) {
  52.                  qu.push(make_pair(temp->left, level-1));
  53.             }
  54.             if (temp->right) {
  55.                 qu.push(make_pair(temp->right, level+1));
  56.             }
  57.         }
  58.         level++;
  59.     }
  60.  
  61.     for (it = hmap.begin(); it != hmap.end(); it++) {
  62.         for (int j = 0; j < it->second.size(); j++) {
  63.             cout << it->second[j] << " ";
  64.         }
  65.         cout << endl;
  66.     }
  67. }
  68.  
  69. int main() {
  70.     Node *root = newNode(5);
  71.     root->left = newNode(3);
  72.     root->right = newNode(7);
  73.     root->left->left = newNode(2);
  74.     root->left->right = newNode(4);
  75.     root->left->left->right = newNode(1);
  76.     root->right->right = newNode(8);
  77.  
  78.     cout<<"Vertical order:"<<endl;
  79.     printVertically (root);
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 5508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Vertical order:
2 
3 1 
5 4 
7 
8
https://ideone.com/lZC7on
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!