Vertical Order Traversal of a Binary tree (Algorithm)

[@mp0157]

It is very difficult to keep a topic simple and yet make it so effective for the audience! You have achieved both! Thank you Vivekanand! This video was very helpful!

[@prasannachalgeri7152]

Vivekanand - Very nice.. I guess if we watch all your videos "many times" then any one could crack any DSA interviews.. There are books in market but they are not as sweet as your explaination.

[@aiswaryajami2841]

Understood the algo in less than 2mins... you are awesome. thank you!!

[@rainegreen4687]

Very clear explanation! This is the first time I watched your video, will surely look for more of these.

[@abhishekgautam1063]

Everything is so nicely explained! Please continue making videos covering maximum topics and fields. Thanks

[@prateektripathi100]

This guy is better than many of the useless books available in the market....hats off to you

[@deepakpai1893]

I saw a lot of solutions for this question, but yours explained it very well. Thanks.

[@pradeepanand5296]

First time watching... Man, u r awesome

[@andreyklysheiko500]

in order to print it there's on more step - order by ascending, because if you print as is you will get a, e, f, b, i, j, c, k, d, g, h, l instead of h, d, b, i, j ..... and so on

[@sachinkulkarni9108]

Hi Vivekanand, The video is really nice and easy to follow. Just one question though.... in the algorithm you described, when we deque the nodes, how are we supposed to get their horizontal distance (h.d.) which is needed to update the h.d. of the left and right child nodes. We can't use the hash table mentioned as the key there is the h.d. and the value is the tree node. So, we can't lookup in the hash table with the node as the key. Wouldn't we need another hash table or some other mechanism to query the h.d. of a given node?

[@amulyareddyg9290]

maybe we can use a queue of pairs of .root's hd is 0 .whenever we deque a node from the queue ,we enqueue its children .So while enqueuing left child it's hd will be one less than its parent node (which we just dequed ..so we already know its hd) similarly when we enqueue its right node its hd is one greater than the parent

[@Blingblingblingling]

video is nicely done. thank you. using any tree traversal should work, filling hash table during traversal. no need for a queue for BFS.

[@akshaybangar7070]

ist's best algo video because you solve problems in easy way.Thanks sir

[@vivekgr3001]

Thanks for excellent explanation! walking through the algorithm line by line!

[@sekharbarua839]

Vivekanand - How do you remmember all the algo.. It is really nice .. I have followed your video and implement the same using Python..

[@chaitu10552]

your explanation covers everything. easy to understand. Thanks

[@saileshverma7353]

Awesome explanation bhaya

[@pawandeepchor89]

Awesome, you guys are so cool !! Keep going !!

[@shreyasmahajan5291]

@Vivekanand Khyade - Algorithm Every Day bhai tuch aapla dada, thank you great explanation!!]

[@aanchalsharma5264]

U deserves to have lakhs of views Keep going and thanks

[@umeshgidnavar8196]

Thanks for very good explanation. I have added code for the same for other people who want code for this algorithm. Current algorithm calculates sum of vertical column order. If just want to display vertical column order then with simple change in code we can achieve that. Thanks. import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Queue; public class VerticalTraversalAndVerticalSum { // From root left child will have parent-1 value for horizontal distance and right child will have // parent+1 horizontal distance. Add them in hashmap checking if it is already there in hashmap // then add values or add new entry public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); root.right.right = new TreeNode(7); Util.printTreeInOrder(root); System.out.println(); Map inOrderColumnSumMap = new HashMap(); findVerticalSumInorderTraversal(root, 0, inOrderColumnSumMap); System.out.println("Vertical column sum using Inorder traversal: " + inOrderColumnSumMap); Map leverOrderColumnSumMap = new HashMap(); findVerticalSumLevelOrderTraversal(root, leverOrderColumnSumMap); System.out .println("Vertical column sum using Lever order traversal: " + leverOrderColumnSumMap); } private static void findVerticalSumLevelOrderTraversal(TreeNode root, Map leverOrderColumnSumMap) { Queue q = new LinkedList(); q.add(root); Map columnValueMap = new HashMap(); columnValueMap.put(root, 0); while (!q.isEmpty()) { TreeNode current = q.poll(); int currentColumnValue = columnValueMap.get(current); if (leverOrderColumnSumMap.containsKey(currentColumnValue)) { leverOrderColumnSumMap.put(currentColumnValue, leverOrderColumnSumMap.get(currentColumnValue) + current.data); } else { leverOrderColumnSumMap.put(currentColumnValue, current.data); } if (current.left != null) { q.add(current.left); columnValueMap.put(current.left, currentColumnValue - 1); } if (current.right != null) { q.add(current.right); columnValueMap.put(current.right, currentColumnValue + 1); } } } // Using inorder keep adding horizontal distance and add sum to Map private static void findVerticalSumInorderTraversal(TreeNode root, int column, Map columnSumMap) { if (root == null) { return; } if (columnSumMap.containsKey(column)) { columnSumMap.put(column, columnSumMap.get(column) + root.data); } else { columnSumMap.put(column, root.data); } // Left child parent-1 as column value findVerticalSumInorderTraversal(root.left, column - 1, columnSumMap); // Right child parent+1 as column value findVerticalSumInorderTraversal(root.right, column + 1, columnSumMap); } } public class TreeNode { public E data; public TreeNode left; public TreeNode right; public TreeNode(E data) { this.data = data; } @Override public String toString() { return "data: "+data; } } public class Util { public static void printTreeInOrder(TreeNode node){ if(node != null){ printTreeInOrder(node.left); System.out.print("["+node.data+"], "); printTreeInOrder(node.right); } } }

[@785_barneetpanda5]

If you could add the code along with explanation, it helps a lot

[@YogeshKumar-px5bd]

Why he has so less subscribers just because he's teaching in an old typical way. No way He definitely deserves subscriber and really good content.

[@rajeshsingh-mv7zn]

Because these are old videos. He stopped uploading regularly and reach went down

[@SatishKanaujiyaeb]

Very nice maza aa gya !!!

[@agniswarbakshi7961]

nice explanation, thanks for the video..please upload some on dynamic programming too :)

[@vivekanandkhyade]

Thanks Agniswar......yes i will upload videos on dynamic programming..!

[@parthsoni7370]

Great Explanation! Thanks

[@argharoy6571]

Excellent explanation

[@ivyxue6443]

very good explanation!! Thank you

[@MohsinKhan-sg8wq]

You Made it very easy to understand using Level order traversal.. Thank you.. But writing code for this approach is more complex because whenever you dequeue an element you need to know the HD value of that node which is not available at the time of getting node from queue. OR I am missing something ?? This can be very easy using recursion.

[@saurabhvemuri5323]

In CPP, You can use queue q; This will store node and its level

[@travelogue4566]

thank so much for nice explanation , great work and keep adding more video .

[@mridulmanohar5940]

Horizontal distance, Hd of each node is stored in the node itself or where? because we need the parent node's HD to compute HD for left or right child node so in a iterative loop it won't work with a local or global variable.

[@dewdropk-dl5tv]

while insertng in the queue, insert with the hd, (object with node and hd for it)

[@saurabhvemuri5323]

In CPP, You can use queue q; This will store node and its level

[@MYUCOZ1]

You can also do this with Pre Order traversal of tree. No need to use Queue as extra storage. Good explanation.

[@every_instant]

Pre Order travelsal + Hash will hav reverse vertical results. Therefore, to achieve top down vertical traversal (higher level nodes appear 1st) we need to traverse by level order.

[@suchitragiri4546]

Very nice explained sir!!

[@quangluong5413]

Is this possible to use preorder traversal instead of level-order traversal? My reason is because the algorithm is based on the horizontal distance of the root node to calculate for children node (which is why inorder, postorder are irrelevant)?

[@vinodrammohan]

Very good explanation. However it would be better if you list the data structures that we would need to create in order to implement this solution. For example, it was not obvious that we need to create a new data structure to store the tree node along with its Hd.

[@TheMihirthakkar]

Thanks for making this video. It helped me a lot :)

[@mdsaif4696]

Bhaiya code de do...

[@ruchimishra2805]

very nice explanation.keep them coming

[@Shashi0012]

Do hashtables allow storing same keys? as you are using hd as the key but multiple nodes have the same hd.

[@saurabhverma3453]

From where you are getting HD of dequeque nodes. Means when you de-queque B, how did you know that HD value for B is -1. You didn't store it anywhere, you are directly calculating it from diagram, but in programming we need to store it somewhere or not?

[@nikhilm4290]

If you do Level order traversal using DFS, then there you can use HD variable as a parameter in recursion. Just wondering how it can be done in BFS.

[@nikhilm4290]

The idea is to make (node, HD) a pair... www.geeksforgeeks.org/print-a-binary-tree-in-vertical-order-set-3-using-level-order-traversal/

[@saurabhverma3453]

@@nikhilm4290 level order traversal using DFS, what does it mean? DFS is for depth search not level. Can u explain it?

[@saurabhverma3453]

@@nikhilm4290 yeah thats what I commented that we need to store HD value of nodes.

[@ok123ut]

Amazing explanation!

[@ArpitDhamija]

there are difficult codes available on google , please upload a simple code here......

[@keyurshah5203]

Nice explaination - easy to implement

[@SiddDev]

hii,thnks for this easy explanation kindly do upload videos on dynamic programming also ....

[@Vj-nu5vx]

please upload algorithms for graph

[@richa6695]

What is the most intuitive answer to this question

[@vikramlucky92]

Code for leetcode 314. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right import collections class Solution: def verticalOrder(self, root: TreeNode) -> List[List[int]]: res = [] if not root: return res seen = {} q = collections.deque() minimum = 0 maximum = 0 q.append([root, 0]) res = [] while q: n = len(q) for i in range(n): node, y_cord = q.popleft() if y_cord in seen: seen[y_cord].append(node.val) else: seen[y_cord] = [node.val] if node.left: q.append([node.left, y_cord - 1]) minimum = min(minimum, y_cord - 1) if node.right: q.append([node.right, y_cord + 1]) maximum = max(maximum, y_cord + 1) for i in range(minimum, maximum + 1): res.append(seen[i]) return res

[@arun26cs]

yes vivek you are super explainatory!!!!!

[@ayaan_faiz]

Great Explanation. Understood it properly. +1 Subscriber. Thanks

[@successally]

Nicely explained thank you sir🙏

[@shreeshametkari7963]

Nice one Sir..

[@vivekanandkhyade]

Thanks Amol Bhai...kasa aahes??

[@smayengbam]

Thank you Sir. Well explained. I salute you 👍

[@piyushjha7222]

sir how to update hd and its corresponding pair in map??

[@amitpadaliya6916]

any idea how to put more than one value in hashmap in java

[@tatianazihindula8762]

at 4:43, what if node 'f' had a left child?? its child's horizontal distance could have been -1 too. any comment on this?

[@MYUCOZ1]

Yes

[@prashantsrivastava9550]

good explanation...thnx

[@VivekSingh-vi3cd]

We have to sort by key to get the final result.

[@Amazi007]

why not use a TreeMap?

[@PrinceKumar-eb8hd]

sir, here we don't know the size of hash table so it varies from (n-1) to -(n-1), this increases the space complexity, moreover, u are inserting the values at the end in the hash table which results in the increase in time complexity. instead of inserting values in last we can insert at the beginning of the node. is there any approach i.e any dynamic implementation using doubly linklist

[@GauravKawatrakir]

is it work for "Vertical Order Traversal of a Binary Tree | leetcode 987' ??

[@harryinsin]

I don't think there is a strict need for level order traversal. A simple recursive inorder traversal would suffice.

[@namrataojha9123]

Nicely explained !!! Could you please cover some videos on dynamic programming ?

[@abhishekmulay]

Thank you Vivekanand. This is a really good explanation for this problem. I have one question, why not insert the nodes in a dictionary/map while traversing the tree instead of using Queue?

[@every_instant]

we need to queue up nodes so that we can traverse by level order. Other traversal algo which dont required queue such as preorder traversal, will yield reverse vertical results

[@shrabanakumar7754]

Sir really helpful videos. I have a request, please categorize the videos which will be helpful to go through based on topics .

[@bhupalibaishya2136]

it's really very nice video and the explanation is so so awesome sir !

[@javi2082]

Hey, the video is nice. Just a suggestion. Please start first with explaining what the question and concept is.

[@TheUmar26]

how to get HD of root in while loop so that can add HD for left and right child ??

[@sanaullah-wu4ww]

very helpful. Thank you!

[@ankitaverma2271]

This video really helped me..

[@karansingh-kp3xg]

Whoever asking code, did you ever google "vertical order traversal of binary tree"?

[@hellostar3063]

how to create a hash table

[@JithendrakumarK]

@@hellostar3063 Since the KEYS we are going to store are unique, we can use unorderdMap here, which stores the unique values and it will not sort either.

[@ayushthakur733]

Telephone rings at 8:35 😂😂😂😂

[@EternalEntity01]

please upload algorithms for m-way search tree and its different operation. your explanation is very nice.thanking u for this great job

[@hussainsaifygaming]

Vivekanand your explanation was very good. I would like to know the code implementation of the above algorithm because the one which I have implemented is with the recursion. Want to know both the ways. Thanks in advance.

[@muditmanchanda1062]

can you please mail me

[@effy1219]

very clear drawing

[@vivekanandkhyade]

Thanks effy..!

[@kkjjllable]

Where can get the sample code?

[@ANJALIGUPTA-vq1cv]

u r awesome sir

[@nandinichouta4119]

Can you please let us know what are the time and space complexity

[@saurabhvemuri5323]

TC:O(N), SC:O(N)

[@rajeshd7389]

What is the Time complexity for this ?

[@Hiteshkumar-fn8gi]

Time complexity O(n)... Space complexity O(n) .. where n is total number of nodes in tree source -> www.geeksforgeeks.org/print-a-binary-tree-in-vertical-order-set-3-using-level-order-traversal/

[@ashvinsrivastava7378]

well done sir

[@Mk-pg5jh]

can u upload the graph algorithm ?

[@vivekanandkhyade]

Yes sure Mohan..!

[@DeepakPandey]

Hi @vivekanand thanks for explanatory videos. Could you please cover trie data structures and there applications. Thanks in advance !

[@vivekanandkhyade]

Thanks Deepak...video on trie data structure is coming soon...!

[@DeepakPandey]

thanks @Vivekanand ... great videos..

[@veerrajuyeleti8541]

sir where can we get the code for this

[@alqudshuriya]

Vivekanand Khyade, thank you for nice explanation.

[@vivekanandkhyade]

Thanks Arham.

[@familyCart]

Can anybody please tell me what would be the time and space complexity of this algorithm?

[@saurabhvemuri5323]

TC:O(N), SC:O(N)

[@prashantnagrurkar2784]

Thank you! Sir.

[@tarunkr.9041]

Gave idea now my turn to write code

[@abhishekjain8869]

awesome veere

[@zenshyam]

The explanation is very good and I am able to understand it too...But i am unable to code that in java....Can someone help me with it.....Thanking you in advance..

[@anjurawat9274]

well explained!!!

[@bhupalibaishya2136]

sir, code please !

[@jiangyucara]

very clear!

[@sahilmotwani9310]

baba tu jhakas hai

[@milimishra6447]

nicely explained........

[@pushpitgill9545]

thank you brother

[@SanTosh-zg2iv]

Please find the code here github.com/santoshr1016/WeekendMasala/blob/master/itsybitsy/TreeDS/simple_tree.py

[@INSPIRINGNMS]

please upload graph algorithms

[@vaibhavjain9094]

sir please make a video on [Print all k-sum paths in a binary tree]

[@anushaghosh7054]

It would have been better if you could attach the codes too

[@27-Joshna]

Yeah

[@rakshith3547]

It would have been better if you had provided the code for your algo

[@thejamadireddy8822]

Any leetcode guys ?

[@DeepakKumar-wu4dt]

Thankyou sir :-)

[@rishabsharma5307]

map mp; void preorder(TreeNode *root, int d) { if(!root) return; mp[d].push_back(root->val); preorder(root->left, d-1); preorder(root->right, d+1); } vector verticalTraversal(TreeNode* root) { mp.clear(); preorder(root, 0); vector vect; for(auto itr = mp.begin(); itr != mp.end(); itr++) { vect.push_back(itr->second); } return vect; }