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)