Vertical Order Traversal of a Binary tree (Algorithm)

[@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.

[@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!

[@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

[@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.

[@aiswaryajami2841]

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

[@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

[@sekharbarua839]

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

[@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); } } }

[@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.

[@shreyasmahajan5291]

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

[@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..!

[@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

[@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!

[@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

[@chaitu10552]

your explanation covers everything. easy to understand. Thanks

[@saileshverma7353]

Awesome explanation bhaya

[@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

[@shrabanakumar7754]

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

[@785_barneetpanda5]

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

[@pradeepanand5296]

First time watching... Man, u r awesome

[@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.

[@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

[@SatishKanaujiyaeb]

Very nice maza aa gya !!!

[@argharoy6571]

Excellent explanation

[@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.

[@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

[@pawandeepchor89]

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

[@suchitragiri4546]

Very nice explained sir!!

[@SiddDev]

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

[@Shashi0012]

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

[@ivyxue6443]

very good explanation!! Thank you

[@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

[@parthsoni7370]

Great Explanation! Thanks

[@aanchalsharma5264]

U deserves to have lakhs of views Keep going and thanks

[@EternalEntity01]

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

[@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.

[@namrataojha9123]

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

[@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

[@travelogue4566]

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

[@keyurshah5203]

Nice explaination - easy to implement

[@successally]

Nicely explained thank you sir🙏

[@arun26cs]

yes vivek you are super explainatory!!!!!

[@ok123ut]

Amazing explanation!

[@richa6695]

What is the most intuitive answer to this question

[@smayengbam]

Thank you Sir. Well explained. I salute you 👍

[@bhupalibaishya2136]

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

[@ruchimishra2805]

very nice explanation.keep them coming

[@GauravKawatrakir]

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

[@Vj-nu5vx]

please upload algorithms for graph

[@harryinsin]

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

[@shreeshametkari7963]

Nice one Sir..

[@vivekanandkhyade]

Thanks Amol Bhai...kasa aahes??

[@prashantsrivastava9550]

good explanation...thnx

[@mdsaif4696]

Bhaiya code de do...

[@arhamzayed8322]

Vivekanand Khyade, thank you for nice explanation.

[@vivekanandkhyade]

Thanks Arham.

[@ArpitDhamija]

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

[@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..

[@VivekSingh-vi3cd]

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

[@Amazi007]

why not use a TreeMap?

[@piyushjha7222]

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

[@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..

[@TheMihirthakkar]

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

[@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.

[@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

[@ankitaverma2271]

This video really helped me..

[@ANJALIGUPTA-vq1cv]

u r awesome sir

[@amitpadaliya6916]

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

[@ayaan_faiz]

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

[@sanaullah-wu4ww]

very helpful. Thank you!

[@ashvinsrivastava7378]

well done sir

[@ayushthakur733]

Telephone rings at 8:35 😂😂😂😂

[@TheUmar26]

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

[@prashantnagrurkar2784]

Thank you! Sir.

[@javi2082]

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

[@effy1219]

very clear drawing

[@vivekanandkhyade]

Thanks effy..!

[@nandinichouta4119]

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

[@saurabhvemuri5323]

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

[@abhishekjain8869]

awesome veere

[@jiangyucara]

very clear!

[@milimishra6447]

nicely explained........

[@anjurawat9274]

well explained!!!

[@pushpitgill9545]

thank you brother

[@rajasekharreddy805]

can you provide the code for this without using recursive ?

[@vaibhavjain9094]

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

[@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/

[@tarunkr.9041]

Gave idea now my turn to write code

[@sahilmotwani9310]

baba tu jhakas hai

[@ankitaverma2271]

thankyousomuch

[@Mk-pg5jh]

can u upload the graph algorithm ?

[@vivekanandkhyade]

Yes sure Mohan..!

[@familyCart]

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

[@saurabhvemuri5323]

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

[@INSPIRINGNMS]

please upload graph algorithms

[@DeepakKumar-wu4dt]

Thankyou sir :-)

[@anushaghosh7054]

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

[@27-Joshna]

Yeah

[@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

[@kkjjllable]

Where can get the sample code?

[@rakshith3547]

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

[@ABHISHEKROY-kd3tw]

8:27 literally shook me xD

[@dhavaljardosh]

me as well

[@bhupalibaishya2136]

sir, code please !

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