Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
@willturner34402 жыл бұрын
Done brother this thing is obvious 😁
@ayushjain3862 жыл бұрын
On 50 line ,i think wha pe parent_track[current]. second aana chaiye because we marked the parents like 5->3 5 ka parent 3 hai
@PrinceKumar-el7ob2 жыл бұрын
@@ayushjain386 no it's correct 5->3 mtlb 5 ka parent 3 hai to parent_track[current] =3 hi aayega if current=5
@JoshMartin472 жыл бұрын
unordered_map in c++ does take O(1) time for look up. so the time complexity in worst case will come out to O(n)
@soumyadeepdas15362 жыл бұрын
Bhaiya for the mark parent function there is probably no need to carry the target node seperately ig?? coz we are just marking the parent nodes for the correspnding child nodes??
@symbol7672 жыл бұрын
To perhaps make it more clear for those still a bit confused He basically turned a Binary Tree into an Undirected Graph, this method is incredible and extremely useful.
@vivekmishra6419 ай бұрын
100 bat ki 1 bat
@someshpatel76606 күн бұрын
Why cant we use DFS and create a mod distance variable which set to 0 at node and going away increment by 1 and on return decrement by 1. When it again comes to node, on return of that node it will -1. Here we can use absolute distance. Thougths?
@aakashpatel1250Күн бұрын
@@someshpatel7660this won't work if the target is on the right subtree and the k distant node is on left subtree of the root. Correct me if I misunderstood
@nopecharon2 жыл бұрын
What i learned: When you have to traverse back use a map to store the parent node
@phatcat7924 Жыл бұрын
these are the comments i look for they straight away go into my revision notes.
@prakhargupta5410 Жыл бұрын
@@phatcat7924 could you please share your notes with us🥺
@tushar8579 Жыл бұрын
@@phatcat7924 Bro he is basically making a graph and doing bfs to reach all nodes at kth level.
@pulkitjain5159 Жыл бұрын
yups
@uRamPlus2 жыл бұрын
Self Notes: 🍋 Mark each node to its parent to traverse upwards 🍋 We will do a BFS traversal starting from the target node 🍋 As long as we have not seen our node previously, Traverse up, left, right until reached Kth distance 🍋 when reached Kth distance, break out of BFS loop and remaining node's values in our queue is our result
@gautamarora65562 жыл бұрын
Thank you
@thinkingmad16852 жыл бұрын
Your self notes help me as well 😄
@shikharbansal29422 жыл бұрын
Helpfull Thanks!
@parthsalat Жыл бұрын
Wherever I go...I search for your "self notes"
@ashishdhal4614 Жыл бұрын
Teach me your ways senpai
@himanshugupta70102 жыл бұрын
We can implement it using recursion as well. As on every node , there will be 3 recursion .. i.e for left , for right and for parent .. code is given below :: void makeParent(TreeNode* root,unordered_map &parent){ queue q; q.push(root); while(!q.empty()){ int n= q.size(); for(int i=0;ileft) { parent[node->left]=node; q.push(node->left); } if(node->right){ parent[node->right]=node; q.push(node->right); } } } } class Solution { public: vector distanceK(TreeNode* root, TreeNode* target, int k) { unordered_map parent; makeParent(root,parent); unordered_map visited; vector ans; solve(target,parent,visited,k,ans); return ans; } void solve(TreeNode* target,unordered_map &parent,unordered_map &visited,int k,vector &ans){ if(k==0){ ans.push_back(target->val); } visited[target]=true; if(target->left && !visited[target->left]){ solve(target->left,parent,visited,k-1,ans); } if(target->right && !visited[target->right]){ solve(target->right,parent,visited,k-1,ans); } if(parent[target]!=NULL && !visited[parent[target]]){ solve(parent[target],parent,visited,k-1,ans); } }
@shubhamuppal-15996 ай бұрын
after doing every question of this series i get to know that main motive is not to prepare for questions in interview/coding round but to identify pattern. Must say striver your content is top notch.
@anujjain92732 жыл бұрын
with this logic , i code code k distance node downwards and upwards, really impressed with the logic , dry run took time , i did it two times though , Thanks for making such content
@shashankojha34522 жыл бұрын
Thanks!
@supratimbhattacharjee53242 жыл бұрын
So basically we are traversing a tree as a graph and doing BFS from the given node
@PrinceKumar-el7ob2 жыл бұрын
yeah forming a graph and doing BFS exactly.
@aman5534 Жыл бұрын
Its kinda funny 😂
@rushidesai2836 Жыл бұрын
Tree is a graph.
@pulkitjain5159 Жыл бұрын
crux : converted tree into an undirected graph and applied a dfs / bfs .
@pratyushnarain52202 жыл бұрын
you can also do it in O(H) space by stroring root to target node path and then calling the k-down function on them.
@nikhilmeena8585 Жыл бұрын
even we can do it without storing the root to that node path , by just checking whether if a nodes leftchild contains target , then we will search for possible answers in the right subtree of current node , and if found in rightNode then w will check possible answers in left subtree , if the node is itself target than we can just see all its childrens at distance k.
@ishangujarathi109 ай бұрын
Superb Intuition and explanation, this problem falls in the range of Hard Problem, but your technique and approach makes it super easy to understand and also code!!
@gandhijainamgunvantkumar67832 жыл бұрын
What an amazing explanation. I was able to do the whole code by myself just after you did a dry run and told the logic. Thank you so much bhaiya for making trees easy for us. :)
@_sf_editz18707 ай бұрын
here is the java code with target as integer and also target as a node thank you striver bhayya for making the concept clearer public class Solution { public static List distanceK(TreeNode root, int target, int k) { Map parent = new HashMap(); markParents(root, null, parent); Queue queue = new LinkedList(); Set visited = new HashSet(); TreeNode tgt = findNode(target , root); queue.offer(tgt); visited.add(tgt); int level = 0; while (!queue.isEmpty()) { if (level == k) break; int size = queue.size(); level++; for (int i = 0; i < size; i++) { TreeNode current = queue.poll(); if (current.left != null && !visited.contains(current.left)) { queue.offer(current.left); visited.add(current.left); } if (current.right != null && !visited.contains(current.right)) { queue.offer(current.right); visited.add(current.right); } TreeNode parentNode = parent.get(current); if (parentNode != null && !visited.contains(parentNode)) { queue.offer(parentNode); visited.add(parentNode); } } } List result = new ArrayList(); while (!queue.isEmpty()) { result.add(queue.poll().val); } Collections.sort(result); return result; } public static void markParents(TreeNode root, TreeNode par, Map parent) { if (root == null) return; parent.put(root, par); markParents(root.left, root, parent); markParents(root.right, root, parent); } static TreeNode findNode(int val , TreeNode root){ if(root==null) return null; if(root.val == val) return root; TreeNode left = findNode(val , root.left); TreeNode right = findNode(val , root.right); if(left==null) return right; if(right == null) return left; return null; } }
@vaibhavgupta9732 жыл бұрын
starting mae toh ache samaj nhi aa rha tha . but jaise hi code walk through kra ... sab samaj aa gaya ache se. Thanks!!
@BinduMahapatra-sq6vhАй бұрын
Ek TVF and dusra TUF bas ye dono hee rocking hai abhi tou.
@armaanhadiq3741 Жыл бұрын
Basically, here we are making the undirected graph from given tree and using BFS(level order traversal of graph) to find different vertices at distance k
@pulkitjain5159 Жыл бұрын
yes
@beamncrash9971 Жыл бұрын
yeah more like creating a adjaceny list and then doing BFS from target node
@harshmittal3128 Жыл бұрын
Thanks for such a great explanation striver... This was a very good question , learnt multiple new approaches from this one ..
@cinime Жыл бұрын
Understood! Such a fantastic explanation as always, thank you very much!!
@gouravkumar74592 жыл бұрын
The easiest explanation for this problem so far on youtube.
@Anonymous-uj3jx2 жыл бұрын
Why everything becomes soo easy when striver teaches it ? Mann you are magical 💖
@AppaniMadhavi4 ай бұрын
ya
@solankiketul56402 ай бұрын
I have one more solution with time complexity O(2n) and space complexity O(n). 1.) Take a map which stores the pair (Node value, direction from root, left or right), eg, (4, left) 2.) in the process, store the level of the target and the direction, level=1, direction= left 3.) if the target is on left, take all the values from level+k with direction left. In our eg, from map[3], we will get 7 and 4 4.) now for ancestor, take map[k-level], so we will have map[1] and as the target value is on left, we will take the nodes with direction right from map[1]. In our example it is 1.
@stith_pragya2 ай бұрын
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@willturner34402 жыл бұрын
For me this is the most awaited video.. Love you striver 😍
@charlesbabbage67863 ай бұрын
What a mind blowing solution!!
@paritoshdadhich295411 ай бұрын
Thank you for the best possible solution. Hats off to your efforts
@NeerajSharma-mz4es2 жыл бұрын
I leanned a new approach thanks to u sir
@deepakjain44819 ай бұрын
i think for this method we should have used 3 pointers in a binary tree left right and parent while constructing tree and then simply traverse the tree and finding the target of the tree and then using a map i which two variable are there int for distance and node for distinct element
@tusharnain66522 жыл бұрын
There is no need of passing target to makr parent function.
@abhineetkapil9 ай бұрын
Nice and easy explaination. !
@palakmantry2 жыл бұрын
Thank you for the explanation, really helpful
@teja1384 Жыл бұрын
if we have to traverse a tree upward then we have to make parent map which store the parent of every node , Nice explanation.
@emmatime20162 жыл бұрын
Soooooo clear !!!! Thank you!
@vanshajtiwari12822 ай бұрын
Love you bhai love you, You are amazing, amazing explaination.
@silicon9794 Жыл бұрын
Good explanation bro. Understood properly. Thankyou :)
@iWontFakeIt2 жыл бұрын
here, the problem in leetcode has constraints given that 0
@bhashkarbelwal41165 ай бұрын
you are amazing tutor #takeuForward bro
@rajatrajgautam32242 ай бұрын
I basically learned if we want to go backward in a tree we need to use a map to store the parent node.........Incredible !
@user-es4vn2uw5l3 ай бұрын
You are magic striver and you create magic
@ayushidalal5488 Жыл бұрын
Amazing explanation! Thankyou so much :)
@sikandarchaudharyzx9014 Жыл бұрын
Sometimes you make the easy questions very complex.
@samyakjain74222 жыл бұрын
just love ur videos man...great explanation...:)
@gubbalamalleswari589210 ай бұрын
Super explanation
@rishabhkumar81152 жыл бұрын
Very well explained bhaiya! understood🔥
@ishachauhan6477Ай бұрын
very well explained thankyou sir
@riteshkhadse45172 жыл бұрын
to mark visited nodes we can use set instead of map.
@aakriti12 жыл бұрын
Understood, Great explanation! 🤩
@amisha25452 жыл бұрын
🔥couldn’t have been better!
@tanishq27668 ай бұрын
I solved it differently(return all the downward nodes at a distance k from some particular node and some simple manipulations), but i think this approach is easier to come up with if someone have studied standard graph problems
@satyamsrivastava90342 жыл бұрын
I encountered this problem in one of the interview I told him the approach which you have explained then he told me not to use the map to store the parents .. and then I shattered as I don't have that approach in mind. :(
@mukulsaluja61092 жыл бұрын
U can store root to target node path
@saikrishnalanka1332 жыл бұрын
In the first step you can find the nodes which are at k distance below given node using recursive traversal. Then back track to each ancestor and store distance of ancestor in variable ( say d). Back track until k-d!=0. and at each ancestor call recursive again to find node at distance k-d.
@chirayubaliyan5181 Жыл бұрын
what about pair, you can use that also!Maybe!
@aryashjain7893 Жыл бұрын
Ill do this again , accha problem hai revision lagega thenks striver
@nagavedareddy58912 жыл бұрын
Perfect and most efficient explanation.. But small optimisation would be using hash set instead of Hashmap for visited.
@chandrachurmukherjeejucse5816 Жыл бұрын
I solved it myself by another approach. Please let me know If It is a good approach or not. 1. Storing the path from root the the node in a deque using a dfs. 2. keep a count for how many elements are popped from deque 2. pop items from the front of deque and find the nodes at a dist (n - no of items popped). 3. Now to make sure that the latter popped node doesnot searches in the direction of the node popped previously we use a unordered set of popped out elements and after finding nodes at a dist for a node we put the node in the unordered set. Code: class Solution { private: bool dfs(TreeNode* root, TreeNode* target, deque &dq) { if(root == NULL) return false; if(root == target) { dq.push_back(target); return true; } bool isFound = false; isFound = dfs(root -> left, target, dq); isFound = isFound || dfs(root -> right, target, dq); if(isFound) { dq.push_back(root); return true; } return false; } void getAllNodes(TreeNode* curr, unordered_set &s, int dist, vector &res) { if(curr == NULL) return; if(s.find(curr) != s.end()) return; if(dist == 0) { res.push_back(curr -> val); return; } getAllNodes(curr -> left, s, dist - 1, res); getAllNodes(curr -> right, s, dist - 1, res); } public: vector distanceK(TreeNode* root, TreeNode* target, int k) { deque dq; unordered_set s; dfs(root, target, dq); vector res; int dist = k; while(!dq.empty()) { TreeNode* curr = dq.front(); dq.pop_front(); getAllNodes(curr, s, dist--, res); s.insert(curr); if(dist < 0) break; } return res; } };
@051-avnee4 Жыл бұрын
Awesome explanation 💫💫!!! Understood .....
@Abhishek-do8mp2 жыл бұрын
just one word - amazing
@theghost9362 Жыл бұрын
ommmg , thanks , I was doing something completely different , I was trying to compute a list that represent that BT , and then compute the the parent and children K times until i get the result , but you're algo is a lot faster
@4747surya9 ай бұрын
Basically convert tree into a undirected graph start from target and do k iteration of BFS ?
@user-tk2vg5jt3l4 ай бұрын
Thank you Bhaiya
@sukhpreetsingh5200 Жыл бұрын
Amazing explanation😇
@nihalnandannayak8869 Жыл бұрын
What is the need of passing target node as argument of the function markparen()
@gigglezone3432 Жыл бұрын
I solved it by converting tree to graph, and take adjacency list and bfs to traverse to all nodes at a distance of k? Is it a good approach for interviews?
@rijumondal68767 ай бұрын
Do I need to go with a brute-better-optimal solution for this approach in the interview if asked??
@Yash-uk8ib2 жыл бұрын
I initiallly thought of actually converting this tree to an undirected graph and just finding K distant nodes but your observation is just best!! Can u tell me why u took visited array??
@takeUforward2 жыл бұрын
So that I dont go back to them..
@Yash-uk8ib2 жыл бұрын
@@takeUforward sir u can visit back only parent nodes right? And that can be maintained using a variable?
@deepaktiwari70592 жыл бұрын
@@Yash-uk8ib We can also revisit the target node from parent node(for eg 3 to 5)
@infinityzero232111 ай бұрын
I am thinking of anotger approach which is treating this like a directed graph. So instead of marking that whuch is the nodes parent we can just make an adj list and mark them like an undirected graph. Then we can directly do the bfs
@mansisethi8127Ай бұрын
Dope question
@pratikdas1780 Жыл бұрын
this is outright amazing. wow! i'm amazed
@pratikdas1780 Жыл бұрын
bro in the past, it's a simple bfs graph traversal technique after you link all the parent nodes. still, it's amazing. just not as hard.
@subhankarpal226011 ай бұрын
Understood... thanks a lot.
@ajitheshgupta30172 жыл бұрын
If it was print all from lead node. What changes has to be done?
@suryakiran29702 жыл бұрын
Great Explanation
@sanchitdeepsingh96637 ай бұрын
thanks sir
@radharamamohanakunnattur3035 Жыл бұрын
Understood!! awesome take
@harshjhunjhunuwala2 жыл бұрын
Actually there's no need of "target" parameter in markParent function as it isn't used anywhere!
@adityaagarwal23242 жыл бұрын
Best explanation 🔥🔥
@AlokKumar-ld9qr2 жыл бұрын
amazing explanation. 😃😃😃
@harshitjaiswal94395 ай бұрын
understood.
@jothsna Жыл бұрын
Nice explanation☺
@lavanyaprakashjampana933 Жыл бұрын
we love your content and we love you.....🖤
@vedantsharma58762 жыл бұрын
Should this(or a similar) question be asked in an interview? Because it took me almost 1 hour to just code!
@amanbhadani88402 жыл бұрын
Yes definitely,You have to work on your speed.
@utkarshsharma66502 жыл бұрын
understooood.thanks :)
@bhaveshkumar68422 жыл бұрын
Thank you bro!!!!
@santanu292 жыл бұрын
Great explanation
@himanshidafouty34723 күн бұрын
Understood
@chiragbansod82525 ай бұрын
understood
@pritamsaha7129 Жыл бұрын
What happens when we get two nodes of same value?? Will unordered map work at that time??
@DevanshuAugusty Жыл бұрын
why are you passing the target node int mark parent function?
@YashKakrecha11 ай бұрын
Wow nice explanation
@littleblackhat2142 Жыл бұрын
How do we solve this without using parent pointers or without any extra space? Is it even possible? I was asked this question in Amazon interview and the interviewer was persistent on solving without space and ultimately it led to me bombing the interview :(
@manojg4451 Жыл бұрын
Love the concept of converting tree to graph, Please do a playlist for bits and sorting
@SUMITKAUSHIK1000 Жыл бұрын
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List distanceK(TreeNode root, TreeNode target, int k) { Map map = new HashMap(); Set visited = new HashSet(); List list = new ArrayList(); updateParent(null, root, map); traverse(k, target, map, list, visited); return list; } public void updateParent(TreeNode parent, TreeNode current, Map childToParent){ if(current == null) return; childToParent.put(current, parent); updateParent(current, current.left, childToParent); updateParent(current, current.right, childToParent); } public void traverse(int distance, TreeNode node, Map childToParent, List list, Set visited){ if(node == null) return; if(visited.contains(node)) return; visited.add(node); if(distance == 0){ list.add(node.val); return; } traverse(distance-1, node.left, childToParent, list, visited); traverse(distance-1, node.right, childToParent, list, visited); traverse(distance-1, childToParent.get(node), childToParent, list, visited); } }
@parthsalat Жыл бұрын
Please do a smooth transition from black iPad to white Code screen...I've become blind because of the quick transition 😥
@rishabsharma53072 жыл бұрын
please make videos on finding time complexity of finding complex questions
@takeUforward2 жыл бұрын
Comes with practice, don't think on that too much :)
@shivampratapsingh218811 ай бұрын
I have one doubt -this above apprach will get fail when tree will not be a binary tree right??
@alesblaze47452 жыл бұрын
thanks mate!
@sakshisinghal1669 Жыл бұрын
Where are we incrementing cur_level after done with the level? Can anyone help?
@prekshaswami3142 Жыл бұрын
why have we taken target as one of the argument in markParents function?
@pritishpattnaik46742 жыл бұрын
Just Excellent
@randeepsaini5491 Жыл бұрын
very helpful
@pranavsharma74792 жыл бұрын
simple bfs traversal on the graph
@agrawalmitesh43958 күн бұрын
GEM
@NoName-hd7okАй бұрын
Store parents and do normal bfs using visited array