Trusted answers to developer questions

Educative Answers Team

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

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

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; }

**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

Copyright Â©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses