# Print Binary tree in vertical order

Problem

Given a Binary tree, print it in vertical order from left to right.

Vertical order for the above Binary tree is:

Vertical order(root):
2
3 1
5 4
7
8

We could solve this problem by performing a breadth-first or level order traversal on the given tree and using a variable ‘level’ to store nodes at same vertical level together in a hash map.

###### Pseudocode
1.  Initialise queue: Q.push(pair(root, level))
2.  while !Q.empty()
3.    node = Q.pop()
4.    node* temp = node.first
5.    int level = node.second
6.    map[level].push(temp->value)
7.    if temp->left != NULL:
8.      Enqueue(Q): Q.push(pair(temp->left, level-1))
9.    if temp->right != NULL:
10      Enqueue(Q): Q.push(pair(temp->right, level+1))
11. iterate over map to print vertical order

Time complexity: O(nlogn)
Auxiliary Space: O(n)

Time complexity could be improved to O(n), if we use a map implementation that allows us O(1) lookups. The C++ map that is used above has O(logn) time complexity.

Code Implementation

//
//  main.cpp
//  Print Binary Tree Vertically
//
//  Created by Himanshu on 25/09/21.
//

#include <iostream>
#include <queue>
#include <map>
using namespace std;

struct node {
int value = 0;
struct node *left, *right;
};
typedef struct node Node;

node* newNode(int data) {
node* Node = new node();
Node->value = data;
Node->left = NULL;
Node->right = NULL;

return (Node);
}

void printVertically (Node *root) {

if (root == NULL) {
return;
}

map<int, vector<int>> hmap;
map<int, vector<int>>::iterator it;
queue<pair<Node*, int>> qu;
int level = 0;

qu.push(make_pair(root, level));

while (!qu.empty()) {
int size = (int) qu.size();
for (int i=0; i<size; i++) {
pair<Node*, int> node = qu.front();
qu.pop();
Node *temp = node.first;
level = node.second;

hmap[level].push_back(temp->value);

if (temp->left) {
qu.push(make_pair(temp->left, level-1));
}
if (temp->right) {
qu.push(make_pair(temp->right, level+1));
}
}

level++;
}

for (it = hmap.begin(); it != hmap.end(); it++) {
for (int j = 0; j < it->second.size(); j++) {
cout << it->second[j] << " ";
}

cout << endl;
}
}

int main() {
Node *root = newNode(5);
root->left = newNode(3);
root->right = newNode(7);
root->left->left = newNode(2);
root->left->right = newNode(4);
root->left->left->right = newNode(1);
root->right->right = newNode(8);

cout<<"Vertical order:"<<endl;
printVertically (root);

return 0;
}


Output

Vertical order:
2
3 1
5 4
7
8 

Here’s a working example: Binary tree (Vertical order)