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.
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 .
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
#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 queueNode* 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 keyif (it->first > maxKey)maxKey = it->first;if (it->first < minKey)minKey = it->first;}printTraversal(umap, minKey, maxKey);}// driver codeint 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;}
printTraversal
function then indexes into the map, using these values, and prints the corresponding nodes in linear time.Free Resources