Related Tags

vertical
order
traversal
map
hashtable

# How to use a vertical order traversal of a binary tree

Vertical order traversal is a method of traversing the elements of a binary tree – from top to bottom and left to right.

## Example

The slideshow below highlights the method and an explanation for each step.

Consider this to be the binary tree for which we need to find a vertical order traversal
1 of 9

## Implementation

The following is an implementation in C++, where C++'s built-in unordered map acts as a hash-table. The algorithm has a time complexity of $O(n)$.

Note: The algorithm can also be used with a normal map, which is sorted in ascending order of keys. However, this causes the time complexity to be $O(n logn).$

#include <queue>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

struct Node {
int value;
Node *left, *right;

Node(int val)
{
this->value = val;
this->left = this->right = NULL;
}
};

void printTraversal(
unordered_map<int, vector<int> > umap,
int minKey, int maxKey)
{
cout << "The vertical order traversal is: " << endl;
for (int i = minKey; i <= maxKey; i++)
{
for (int j=0;j<umap[i].size();j++)
{
cout << umap[i][j] << " " ;
}
cout << endl;
}
}

void verticalOrderTraversal(Node* root)
{
if (root == NULL)
return;

unordered_map<int, vector<int> > umap;
queue<pair<Node*, int>> q;

q.push({root, 0}); // the horizontal distance of the root is 0.

while (!q.empty())
{
// pop front node from the queue
Node* node = q.front().first;
int dist = q.front().second;
q.pop();

// insert in the correct hash value in the table.
umap[dist].push_back(node->value);
// push its children, if any, into the queue.
if (node->left)
q.push({node->left, dist - 1});
if (node->right)
q.push({node->right, dist + 1});
}

cout << "The unordered hashmap is:" << endl;
unordered_map< int,vector<int> > :: iterator it;
// if we get to know the min and max key,
// then we can print the vertical traversal in
// linear time as well.
int maxKey = 0;
int minKey = INT_MAX;
for (it=umap.begin(); it!=umap.end(); it++)
{
cout << it->first << ": ";
for (int i=0; i<it->second.size(); ++i)
cout << it->second[i] << " ";
cout << endl;

// finding the min and max key
if (it->first > maxKey)
maxKey = it->first;
if (it->first < minKey)
minKey = it->first;
}

printTraversal(umap, minKey, maxKey);
}

// driver code
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->right->left = new Node(4);
root->right->right = new Node(5);
root->right->left->left = new Node(6);
root->right->left->right = new Node(7);
root->right->left->right->left = new Node(8);
root->right->left->right->right = new Node(9);
verticalOrderTraversal(root);
return 0;
}

## Explanation

• Line 41: A key-value pair of the root, consisting of its horizontal distance and value, is pushed into a queue.
• Lines 43-57: Each node from the queue is first removed. Then, it is inserted in the unordered map with its distance as the key. Its children are then enqueued with the correct values of distance. This process continues until the queue is empty (i.e. all nodes have been processed).
• Lines 74-77: This is an optimization step, where the maximum and minimum keys in the map are found. The printTraversal function then indexes into the map, using these values, and prints the corresponding nodes in linear time.

RELATED TAGS

vertical
order
traversal
map
hashtable