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!
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); } } }
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
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.
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
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
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)?
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.
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
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.
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.
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.
@@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.
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..
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/
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
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!
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.
I saw a lot of solutions for this question, but yours explained it very well. Thanks.
Understood the algo in less than 2mins... you are awesome. thank you!!
Thanks for excellent explanation! walking through the algorithm line by line!
video is nicely done. thank you. using any tree traversal should work, filling hash table during traversal. no need for a queue for BFS.
ist's best algo video because you solve problems in easy way.Thanks sir
your explanation covers everything. easy to understand. Thanks
Awesome, you guys are so cool !!
Keep going !!
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);
}
}
}
First time watching... Man, u r awesome
thank so much for nice explanation , great work and keep adding more video .
@Vivekanand Khyade - Algorithm Every Day bhai tuch aapla dada, thank you great explanation!!]
This guy is better than many of the useless books available in the market....hats off to you
U deserves to have lakhs of views
Keep going and thanks
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
Nicely explained !!!
Could you please cover some videos on dynamic programming ?
please upload algorithms for m-way search tree and its different operation. your explanation is very nice.thanking u for this great job
very nice explanation.keep them coming
nice explanation, thanks for the video..please upload some on dynamic programming too :)
Thanks Agniswar......yes i will upload videos on dynamic programming..!
Thank you Sir. Well explained. I salute you 👍
Great Explanation! Thanks
Vivekanand - How do you remmember all the algo.. It is really nice .. I have followed your video and implement the same using Python..
it's really very nice video and the explanation is so so awesome sir !
Sir really helpful videos. I have a request, please categorize the videos which will be helpful to go through based on topics .
very good explanation!! Thank you
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.
Thanks for making this video. It helped me a lot :)
yes vivek you are super explainatory!!!!!
Great Explanation. Understood it properly. +1 Subscriber. Thanks
Amazing explanation!
Nice explaination - easy to implement
Awesome explanation bhaya
Very nice explained sir!!
Nicely explained thank you sir🙏
Very nice maza aa gya !!!
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
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
Excellent explanation
how to get HD of root in while loop so that can add HD for left and right child ??
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)?
please upload algorithms for graph
sir how to update hd and its corresponding pair in map??
Do hashtables allow storing same keys? as you are using hd as the key but multiple nodes have the same hd.
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
If you could add the code along with explanation, it helps a lot
very helpful. Thank you!
hii,thnks for this easy explanation kindly do upload videos on dynamic programming also ....
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.
What is the most intuitive answer to this question
any idea how to put more than one value in hashmap in java
good explanation...thnx
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
This video really helped me..
Bhaiya code de do...
Vivekanand Khyade, thank you for nice explanation.
Thanks Arham.
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
nicely explained........
Thank you! Sir.
is it work for "Vertical Order Traversal of a Binary Tree | leetcode 987' ??
I don't think there is a strict need for level order traversal. A simple recursive inorder traversal would suffice.
please upload graph algorithms
sir please make a video on [Print all k-sum paths in a binary tree]
well done sir
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
can you provide the code for this without using recursive ?
well explained!!!
Nice one Sir..
Thanks Amol Bhai...kasa aahes??
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
there are difficult codes available on google , please upload a simple code here......
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..
sir where can we get the code for this
u r awesome sir
awesome veere
very clear!
very clear drawing
Thanks effy..!
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
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.
Where can get the sample code?
We have to sort by key to get the final result.
why not use a TreeMap?
thank you brother
Can you please let us know what are the time and space complexity
TC:O(N), SC:O(N)
Can anybody please tell me what would be the time and space complexity of this algorithm?
TC:O(N), SC:O(N)
Gave idea now my turn to write code
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..
baba tu jhakas hai
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.
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/
can u upload the graph algorithm ?
Yes sure Mohan..!
Thankyou sir :-)
thankyousomuch
sir, code please !
Hey, the video is nice. Just a suggestion.
Please start first with explaining what the question and concept is.
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
Please find the code here
github.com/santoshr1016/WeekendMasala/blob/master/itsybitsy/TreeDS/simple_tree.py
It would have been better if you had provided the code for your algo
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;
}
pls give the code also !!!!