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 .
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;}
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
printTraversalfunction then indexes into the map, using these values, and prints the corresponding nodes in linear time.
Free Resources
Copyright ©2025 Educative, Inc. All rights reserved