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.
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!
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
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); } } }
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?
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
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.
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.
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.
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.
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)?
@@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.
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
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?
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
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.
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..
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
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?
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/
![[#2024MAMA] G-DRAGON - 무제(Untitled, 2014)+POWER+HOME SWEET HOME+뱅뱅뱅+FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/Ox29z5Nf1Uk/mqdefault.jpg)
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.
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!
video is nicely done. thank you. using any tree traversal should work, filling hash table during traversal. no need for a queue for BFS.
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
Understood the algo in less than 2mins... you are awesome. thank you!!
This guy is better than many of the useless books available in the market....hats off to you
Everything is so nicely explained!
Please continue making videos covering maximum topics and fields.
Thanks
Very clear explanation! This is the first time I watched your video, will surely look for more of these.
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);
}
}
}
ist's best algo video because you solve problems in easy way.Thanks sir
@Vivekanand Khyade - Algorithm Every Day bhai tuch aapla dada, thank you great explanation!!]
I saw a lot of solutions for this question, but yours explained it very well. Thanks.
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?
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
Vivekanand - How do you remmember all the algo.. It is really nice .. I have followed your video and implement the same using Python..
If you could add the code along with explanation, it helps a lot
Thanks for excellent explanation! walking through the algorithm line by line!
your explanation covers everything. easy to understand. Thanks
You can also do this with Pre Order traversal of tree. No need to use Queue as extra storage. Good explanation.
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.
Bhaiya code de do...
Awesome explanation bhaya
very good explanation!! Thank you
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.
Because these are old videos. He stopped uploading regularly and reach went down
First time watching... Man, u r awesome
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.
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.
In CPP, You can use queue q; This will store node and its level
Great Explanation! Thanks
Excellent explanation
please upload algorithms for graph
nice explanation, thanks for the video..please upload some on dynamic programming too :)
Thanks Agniswar......yes i will upload videos on dynamic programming..!
Very nice maza aa gya !!!
Awesome, you guys are so cool !!
Keep going !!
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.
while insertng in the queue, insert with the hd, (object with node and hd for it)
In CPP, You can use queue q; This will store node and its level
hii,thnks for this easy explanation kindly do upload videos on dynamic programming also ....
U deserves to have lakhs of views
Keep going and thanks
Very nice explained sir!!
We have to sort by key to get the final result.
why not use a TreeMap?
Sir really helpful videos. I have a request, please categorize the videos which will be helpful to go through based on topics .
Nice explaination - easy to implement
What is the most intuitive answer to this question
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)?
Do hashtables allow storing same keys? as you are using hd as the key but multiple nodes have the same hd.
Amazing explanation!
I don't think there is a strict need for level order traversal. A simple recursive inorder traversal would suffice.
Hey, the video is nice. Just a suggestion.
Please start first with explaining what the question and concept is.
yes vivek you are super explainatory!!!!!
Nicely explained thank you sir🙏
there are difficult codes available on google , please upload a simple code here......
Whoever asking code,
did you ever google "vertical order traversal of binary tree"?
how to create a hash table
@@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.
very nice explanation.keep them coming
please upload algorithms for m-way search tree and its different operation. your explanation is very nice.thanking u for this great job
Thanks for making this video. It helped me a lot :)
thank so much for nice explanation , great work and keep adding more video .
Nicely explained !!!
Could you please cover some videos on dynamic programming ?
This video really helped me..
sir how to update hd and its corresponding pair in map??
Thank you Sir. Well explained. I salute you 👍
Nice one Sir..
Thanks Amol Bhai...kasa aahes??
it's really very nice video and the explanation is so so awesome sir !
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
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?
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
good explanation...thnx
Vivekanand Khyade, thank you for nice explanation.
Thanks Arham.
Hi @vivekanand thanks for explanatory videos.
Could you please cover trie data structures and there applications. Thanks in advance !
Thanks Deepak...video on trie data structure is coming soon...!
thanks @Vivekanand ... great videos..
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.
can you please mail me
very helpful. Thank you!
sir please make a video on [Print all k-sum paths in a binary tree]
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..
Great Explanation. Understood it properly. +1 Subscriber. Thanks
very clear drawing
Thanks effy..!
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
is it work for "Vertical Order Traversal of a Binary Tree | leetcode 987' ??
any idea how to put more than one value in hashmap in java
u r awesome sir
how to get HD of root in while loop so that can add HD for left and right child ??
please upload graph algorithms
well done sir
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?
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.
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/
@@nikhilm4290 level order traversal using DFS, what does it mean? DFS is for depth search not level. Can u explain it?
@@nikhilm4290 yeah thats what I commented that we need to store HD value of nodes.
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?
Yes
Gave idea now my turn to write code
It would have been better if you could attach the codes too
Yeah
Can you please let us know what are the time and space complexity
TC:O(N), SC:O(N)
Thank you! Sir.
awesome veere
very clear!
nicely explained........
thank you brother
Telephone rings at 8:35 😂😂😂😂
well explained!!!
Can anybody please tell me what would be the time and space complexity of this algorithm?
TC:O(N), SC:O(N)
can u upload the graph algorithm ?
Yes sure Mohan..!
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;
}
It would have been better if you had provided the code for your algo
baba tu jhakas hai
sir, code please !
Thankyou sir :-)
What is the Time complexity for this ?
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/
thankyousomuch
Where can get the sample code?
8:27 literally shook me xD
me as well
sir where can we get the code for this