L21. Vertical Order Traversal of Binary Tree | C++ | Java

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

[takeUforward]

Hi, hope you are well.


Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL and many other time saving features under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing yourself.

[vashishthsharma]

if you are solving this problem on GFG change two things
1. instead of using multiset use a vector.
2. copy the vector of vector (ans) into a 1d vector, return the 1d vector.
at last thank u Raj bhaiya, great work.

[aayushgoswami]

for(auto p:nodes){
vector<int>col;
for(auto q:p.second){
for(int it: q.second){
col.push_back(it);
}
}
ans.push_back(col);
}
use this if u didin't understood col.insert thing.

[_anurag]

Wow after this wonderful explanation!! preorder approach became too easy.
Here is the code :-
void preorder(TreeNode* node, int vertical, int level, map<int, map<int, multiset<int>>> &nodes){
if(node == nullptr) return;


preorder(node->left, vertical-1, level+1, nodes);
preorder(node->right, vertical+1, level+1, nodes);
}

vector<vector<int>> verticalTraversal(TreeNode* root) {
map<int, map<int, multiset<int>>> nodes;
preorder(root, 0, 0, nodes);
vector<vector<int>> ans;

for(auto p:nodes){
vector<int> col;
for(auto q:p.second){
col.insert(col.end(), q.second.begin(), q.second.end());
}
ans.push_back(col);
}


return ans;
}

[MischievousSoul]

One of the hardest question in the whole playlist.. Took a whole day to understand and write the code..
But ig its fair to not rush and just devote the req time to some questions..

[asishcodes]

4:37 There is a small typo, the co-ordinates of the rightmost node is actually (2, 2) not (1, 2)

[ravindrabarthwal]

I'm enrolled in Coding Ninjas Competitive Programming Premium course. Your content has much more depth than CN. <3

[soumikdutta]

The GFG variant of this question is a bit easy. In the GFG variant you don't need to sort the elements, just add the elements in the ans. as it is in the tree.

[bestdeal]

for those having difficulty in the last part can use this code segment ( just elaborated a bit for easy understanding ) 😊😊
vector<vector<int>> ans;
for(auto it:m)
{
vector<int> v;
for(auto t:it.second)
{
for(auto x:t.second)
{
v.push_back(x);
}
}
ans.push_back(v);
}
return ans;
}

[anonymousvoid]

Hey everyone! Welcome back to the channel. I hope you guys are doing well!
My mind gets fresh whenever i hear this from strivers mouth.

[dikshasonia]

i think this is the hardest question of this playlist till it really required like 1 day to understand this and code it.

[babulalyadav]

00:02 Introduction to vertical order traversal in binary tree
02:13 Understand the concept of vertical order traversal in a binary tree
04:32 Traversing and assigning verticals and levels to every node
06:39 Using multiset to store multiple notes for each level
08:51 Understanding the vertical order and level change during level order traversal
10:49 Vertical order traversal involves tracking node positions
12:49 Storing vertical orders using data structures
15:04 Explaining vertical order traversal in Java
17:00 Explanation of time and space complexity for vertical order traversal
18:38 Subscribe for upcoming series
Crafted by Merlin AI.

[subhamtulshan]

Here the Time Complexity will be o(nlogN), as we are using TreeMap and each operation in treeMap takes logN time. We can use DLL to solve it in O(N). where each node in DLL is like (data -> list of element, next -> points to the next verticle, prev-> points to the previous vertical)

[jashanbansal]

Can be solved using map<int, vector<int>>
We r going level by level only, so nodes would be inserted from top to bottom, therefore no need to maintain level

[ANANDCHAPKE]

Timestamps (Powered by Merlin AI)
00:02 - Introduction to vertical order traversal in binary tree
02:13 - Understand the concept of vertical order traversal in a binary tree
04:32 - Traversing and assigning verticals and levels to every node
06:39 - Using multiset to store multiple notes for each level
08:51 - Understanding the vertical order and level change during level order traversal
10:49 - Vertical order traversal involves tracking node positions
12:49 - Storing vertical orders using data structures
15:04 - Explaining vertical order traversal in Java
17:00 - Explanation of time and space complexity for vertical order traversal
18:38 - Subscribe for upcoming series

[fahrenheit]

absolutely amazing explanation, learned a lot more than tree traversal in this video (my STL is not the best)

[shlokdubey]

For those having difficulty in understanding map and multisets, check this out, logic is same..(used sorting)

static bool comp(vector<int> &a, vector<int> &b) {
if(a[0]==b[0] && a[1]==b[1]) {
return a[2]<b[2];
}
else if(a[1]==b[1]) {
return a[0]<b[0];
}
return a[1]<b[1];
}


vector<vector<int>> verticalTraversal(TreeNode* root) {
vector<vector<int>> res;
if(root==NULL) {
return res;
}
vector<vector<int>> temp;
queue<TreeNode*> q;
q.push(root);
temp.push_back({0, 0, root->val});
int index=0;
while(!q.empty()) {
TreeNode* node=q.front();
q.pop();
if(node->left) {
q.push(node->left);
temp.push_back({temp[index][0]+1, temp[index][1]-1, node->left->val});
}
if(node->right) {
q.push(node->right);
temp.push_back({temp[index][0]+1, temp[index][1]+1, node->right->val});
}
index++;
}
sort(temp.begin(), temp.end(), comp);
vector<int> v;
v.push_back(temp[0][2]);
int cur_col=temp[0][1];
for(int i=1;i<temp.size();i++) {
if(cur_col==temp[i][1]) {
v.push_back(temp[i][2]);
}
else {
res.push_back(v);
v.clear();
v.push_back(temp[i][2]);
cur_col=temp[i][1];
}
}
res.push_back(v);
return res;
}

[lone_wolf]

man the explaination is masterclass..
hats off to you ..
at first i have a problem but as you suggested to dry run i have done and now its crystal clear

[gitanjalikumari]

Thank you so much for explaining the C+++ code..after lot of searching I found this video and it's awesome

[coding]

Ctr + right arrow, for shifting the chapter of ads in video