Introduction
In this blog, we will be discussing map and preorder traversal-based methods to print a binary tree in vertical order. We already have the basic method to print a binary tree in vertical order in this blog. Check it out to learn the basic method and understand the problem thoroughly.
Also see, Iterative Preorder Traversal of Trees
Before diving into the solution, let's again have a brief look at the problem. Suppose we have the following binary tree, and we need to print it in vertical order.
On printing the binary tree given above, we will get the following output -
|
9 4 2 6 5 7 3 8 1 |
We can observe from the output that we need to print the leftmost node in the tree, then the next leftmost node, and so on. And if two or more nodes are equally distant from the root, we print them in top-to-bottom order. Though the map-based solution is faster, it couldn't fulfill this criterion. We will learn another approach based on the preorder traversal of a binary tree, which fulfills this criterion. So, let's begin with the map-based method.
The map-based approach
This approach to printing a binary tree in vertical order uses a hashmap of vectors of horizontal distance vs. an array of nodes having equal horizontal distance values. So, we start with traversing the tree, finding each node's horizontal distance, and inserting them into the map by appending them to the array corresponding to their key's value. Then we iterate through the map in the increasing order of the keys and print the array of associated nodes.
Algorithm for the map-based approach
- Create a binary tree or take it as input from the user.
- Create a map to store horizontal distance and an array of nodes with that distance as key-value pairs.
- Traverse the tree and keep appending nodes in the array associated with their distance from the root.
- Traverse the map to print all the arrays of nodes stored in the map.
Implementation of the map-based approach
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *left, *right;
};
//To create a new node for the binary tree.
node *createnode(int data)
{
node *var = new node;
var->data = data;
var->left = var->right = NULL;
return var;
}
//Function to find the nodes at a hordist and push
//them in to the map.
void togetverticalorder(node* root, int hordist, map<int, vector<int>>&mp)
{
//Base case.
if(root==nullptr)
{
return;
}
//To push the node into the vector corresponding
//to its hoizontal distance.
mp[hordist].push_back(root->data);
//Make recursive calls for the left and right
//subtrees.
togetverticalorder(root->left, hordist-1, mp);
togetverticalorder(root->right, hordist+1, mp);
}
//Function to create a map, then get the vertical
//order of the tree by calling above function, then
//printing.
void vertiorder(node *root)
{
//Creating a map.
map<int,vector<int>> mp;
int hordist=0;
togetverticalorder(root, hordist, mp);
//To print the values in the map.
map< int,vector<int> > :: iterator itr;
for(itr=mp.begin(); itr!=mp.end(); itr++)
{
for(int i=0;i<itr->second.size();++i)
cout << itr->second[i] << " ";
cout << endl;
}
}
//Driver function.
int main()
{
//Creating the binary tree.
node *root=createnode(5);
root->left=createnode(2);
root->right=createnode(8);
root->left->left=createnode(4);
root->left->right=createnode(7);
root->right->left=createnode(3);
root->right->right=createnode(11);
root->left->left->left=createnode(9);
root->left->left->right=createnode(6);
vertiorder(root);
return 0;
}
Output-
|
9 4 2 6 5 7 3 8 11 |
The time complexity of the above approach is O(N*log(N)), where N is the number of nodes in it, as the map in STL takes O(log(N)) time for all the operations, and we processed all the N nodes.
The space complexity of the above approach is O(N).
24+ registered 
