Can you please help me out on this as this question is asked in my interview @takeUforward AMY AND SCHOOL Problem Statement Wizard-Land can be represented as infinite line with coordinates ….., -3, -2, -1, 0, 1, 2, 3 … and so on. Amy teaches in a school with N batches of students. Ai denotes the number of students in the ith batch. Amy has to choose one coordinate as school and one coordinate for each batch of students as their hostel. Students of same batch lives in one hostel. All the N+1, coordinates chosen by her must be distinct. Each morning students walks from their hostel to the school. If the student’s hostel is at coordinate XH and school is at coordinate XS, then he travels | XS - XH | units of distance. She wants to assign these N+1, coordinates such that total distance travelled by each student to reach the school in morning is minimized. Find the minimum total distance. You are given T independent test cases. Constraints 1
Every other TH-camr just speaks the code out, it's only you who focus on explaining the question by manually drawing and dry running it. That's the identity of a real hero. Thanks a lot.
@@dikshasoni52a98 Because If 7 is on left of 4 then 4 will be LCA .So no need to go down as we will either get NULL or p or q or some common node (root) nothing else
Understood!! PS:- You will be given a two nodes and you need to return LCA of those two nodes. Solution approach:- Use DFS traversal(Recursive DFS) first go to left and then go to right. 0) If the root node is only one the node which you are looking for then return root 1) If both left and right returns null then returns null 2) If left returns a node and right returns null then return left and vice versa (Return something which gives u node) 3) If both returns you the nodes then u have found the answer so return root Code:- class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null || root==p || root==q){ return root; } TreeNode left=lowestCommonAncestor(root.left,p,q); TreeNode right=lowestCommonAncestor(root.right,p,q); if(left==null){ return right; } else if(right==null){ return left; } else{ return root; } } }
Your explanations are truly remarkable and have greatly helped me in understanding complex concepts more clearly. Your dedication to simplifying intricate topics and your engaging teaching style make learning DSA both enjoyable and enlightening. Take love sir.
I could never think, of such a great Idea. I approached this probelm in different way. We can level order traverse each node to find the nodes parent and the level they are in. so, for the given 2 nodes, the node which is higher level can be taken up to the level of node in lower level. After this, in each iteration of leel decrement, keep check if we found a mtach between those 2 node. if yes, return the answer, other wise, keep decrementing level, by moving to the parent node.
In the third case, i guess lca(2,6) would be 1 because the proper ancestor of n is any node y such that node y is an ancestor of node n and y is not the same node as n.
Hey striver, Space Complexity of first approach should O(H) for each call because at maximum we can have nodes equal to the height of the tree. Thanks for the lecture.
@@renukasubramaniyam754 I think it was mentioned in question that both nodes are present. However, even if it's not mentioned, we can have 2 flags found1 and found2, and iterate once to see if both are present. And if anyone or both are not present, we can return null without performing actual logic.
@@takeUforward hey then if the question comes likes print the path from one node to the other one including the lca (which will be a distinct path) this approach would not work right? then the brute force approach is needed right?
hey striver, I really like ur videos because of the clarity with whick you teach. However, this video lacked clarity, as i wasnt convinced why would that case work where lca(x, y) is x. However it worked, and after doing some dry runs i understood why it worked but you didnt cover this case in the examples. Just a positive feedback 😄
The solution was great but I think it wont give right answer if the other node is not in the tree. In that case we have to do brute force only I think. Edit: I just saw the leetcode question of this video and it was mentioned that it is guaranteed that p and q will be present in the tree.
Intuition: Consider a node as a potential answer (LCA). If both left and right subtrees return non-null values, it means both nodes p and q have been found in different subtrees, confirming that this node is indeed the LCA. Now, consider a node that is not the answer. In this case, either the left or right subtree (or both) will return null. However, if one of them is not null, it indicates that one of the nodes (p or q) has been found, and this information will be passed up the tree to potentially contribute to identifying the LCA at a higher level. class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null || root.val==p.val || root.val==q.val){ return root; }
To save people time, In this video he only explained one case where you will get one element in left side and one in right. but there are also some cases, Consider that we have both the elements in left side of subtree? or there is no element present etc. So this is not the video I was looking for I like to understand every possible case.
Thansk a lot for both approaches.............Most of us think that ....what if p and q both on the same path then ?... Like if p and q on the same path then, first whether p or q meet on that path and return that and no need to go further onthat path and all other root will then return null ...SO as Striver said, if either of null then we return value part.. so we got answer in this case too. Can there will be a duplicate node too @striver?
As soon as node 8 is encountered, it returns its value to the parent node and we don't even need to check for 7 bcoz in that case 7 will lie in the subtree rooted at node 8.
Looking at comments I think I am the only one who got another idea apart from this recursive approach. The intuition is to use property of BST. the right of node will contains elements > root and left of nodes will contains elements < root. So you can use this to find the solution iteratively.
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
Understooooooooooooooood :)
and done everything thank u so much striver :)
Do TreeNode* left and right take space? I mean definitely there's pointer to heap/ dynamically
Will this approach work if numbers are not present in the tree?
done bro
Can you please help me out on this as this question is asked in my interview @takeUforward
AMY AND SCHOOL
Problem Statement
Wizard-Land can be represented as infinite line with coordinates ….., -3, -2, -1, 0, 1, 2, 3 … and so on. Amy teaches in a school with N batches of students. Ai denotes the number of students in the ith batch.
Amy has to choose one coordinate as school and one coordinate for each batch of students as their hostel. Students of same batch lives in one hostel. All the N+1, coordinates chosen by her must be distinct.
Each morning students walks from their hostel to the school. If the student’s hostel is at coordinate XH and school is at coordinate XS, then he travels | XS - XH | units of distance.
She wants to assign these N+1, coordinates such that total distance travelled by each student to reach the school in morning is minimized. Find the minimum total distance.
You are given T independent test cases.
Constraints
1
Every other TH-camr just speaks the code out, it's only you who focus on explaining the question by manually drawing and dry running it. That's the identity of a real hero. Thanks a lot.
I watched about 4 minutes of your video and coded it myself.. Your explanation is just heaven .
but the real part starts after 4minutes😂
@@als_venky7057 😂😂
@@als_venky7057 xD 😂😂😂😂
@@als_venky7057 😅😅
that approach should not be done..
watch the latter half for the optimal approach
Best solution,
After 5 minutes of understanding, I got that why we don't need to go forward after getting anyone of the descendants.
hats off🤠
Can u tell why we don't have to go further ... I didn't get it ........ What if 7 is on left or right of 4 ......
@@dikshasoni52a98 Because If 7 is on left of 4 then 4 will be LCA .So no need to go down as we will either get NULL or p or q or some common node (root) nothing else
I tried to understand the logic by myself for 2 times and then coded it without seeing anyone's code. Feeling so good💗
heyy same, but why are you here then🤔
@@electronx5594 Just to comment this. 😄
Striver bhai rocked.. buddy you are helping thousands of folks like me preparing for DSA interview. :)
hey @take U forward, i dont usualy comment here but its really motivating to see you hustle so much. We get to learn a lot from your personality.
Thanks a lot for contributing to the community.
Nicely understood!!!
Understood!!
PS:- You will be given a two nodes and you need to return LCA of those two nodes.
Solution approach:- Use DFS traversal(Recursive DFS) first go to left and then go to right.
0) If the root node is only one the node which you are looking for then return root
1) If both left and right returns null then returns null
2) If left returns a node and right returns null then return left and vice versa (Return something which gives u node)
3) If both returns you the nodes then u have found the answer so return root
Code:-
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root==p || root==q){
return root;
}
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left==null){
return right;
}
else if(right==null){
return left;
}
else{
return root;
}
}
}
best explanation till date!!Vey very very easily understood as a noob coder.Thanks a lot!!
Classic binary tree question! Thanks Striver.
Your explanations are truly remarkable and have greatly helped me in understanding complex concepts more clearly. Your dedication to simplifying intricate topics and your engaging teaching style make learning DSA both enjoyable and enlightening. Take love sir.
The best explantion 🔥🔥🔥🏅 really loved it🔥🔥I must say this is your best video
I never comment on vedio, but this was extremely sweet to go uncommented.
I love how you articulate every step, you are a saviour brother
i am solving question by myself without watching lec bcoz of youre awosome lectures thank you keep it up!!
Simple and lucid explanation. Thanks, bro.
the optimized approach was awesome, loves the intuition !!! easyily understood
Understood,able to solve by brute force and with optimized approach after getting a hint.Thank you striver
Such a cool teaching... and an awesome logic.
I could never think, of such a great Idea.
I approached this probelm in different way.
We can level order traverse each node to find the nodes parent and the level they are in.
so, for the given 2 nodes, the node which is higher level can be taken up to the level of node in lower level. After this, in each iteration of leel decrement, keep check if we found a mtach between those 2 node.
if yes, return the answer, other wise, keep decrementing level, by moving to the parent node.
what is thought was of do two dfs for each node notice the path of each and then run a check on the path of the string
Amazing man.. the last line was what i was not able to understand, i.e. if both are not null,then return root. Thankyou bro.
Explanation is flawless. keep it up.
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Nicely explained and easily underatood
In the third case, i guess lca(2,6) would be 1 because the proper ancestor of n is any node y such that node y is an ancestor of node n and y is not the same node as n.
Never thought that the solution for this question will be so simple and easy to understand.
Bhai ismei simple kya tha 😢
Wow I was able to write the code myself just after explanation.
one of the good binary tree problem
I've watched this video 5 times to understand the concept 😅.
Just want to thank u bhaiya for such an fabulous explanation and amazing content.
Thank you so much Striver !
Thankyou for amazing solution Striver
u work is really helping us to understand this type of concept. So thank u !!
striver sir you are op what is extreme level solution 😍😍😍😍well this is my first comment in your channel because you do a very good job
your on a different level !!! thank you 💎
Understood! Super amazing explanation as always, thank you very much!!
Great Explanation, loving the series so far
too smooth too good...amazing explanation...thank you STRIVER
superb explanation!!! it made trees very easy for me. Thank you so much.
Striver ,your videos are perfect.
Beautifully explained!!
Totally clear, loving this series. Thanks a ton for making this.❤️
Well illustrated. Thanks
great video .... very nicely explained ...... just loved it ❤
UNDERSTOOD! THANK YOU🙌
Hey striver, Space Complexity of first approach should O(H) for each call because at maximum we can have nodes equal to the height of the tree. Thanks for the lecture.
tree question are very easy after watching your lecture. thanks bhayia
Next level explaination💯
Commenting to increase count +1 , Nice collection of videos.
Overwhelming explanation 👏👏👏👏 bhaiya 🥳🥳🥳
Understood ❤
very well explained !! Thanks
you got new subscriber . outstanding explanation !🙂
thanks bro, your dry run was great,, was struggling to visualize recurssion
Crystal clear explanation !!
Completed 28/54 (51%) done!!!
You are so good. Thank you!
nice bro keep it up you are our motivation😎😎😎
@10:08 you returned when you found 8, but what if 7 is present in 8's subtree, that is not explored?
Then 8 will only be the lca na even if 7 is under subtree. So why to go deep
What if 7 is not present in the tree at all
@@renukasubramaniyam754 I think it was mentioned in question that both nodes are present. However, even if it's not mentioned, we can have 2 flags found1 and found2, and iterate once to see if both are present. And if anyone or both are not present, we can return null without performing actual logic.
@@takeUforward hey then if the question comes likes print the path from one node to the other one including the lca (which will be a distinct path) this approach would not work right? then the brute force approach is needed right?
beautiful explanation my man.
this is just perfect
Thank you :)))) Was nicely explained.
Best ever solution for this problem!
hey striver, I really like ur videos because of the clarity with whick you teach. However, this video lacked clarity, as i wasnt convinced why would that case work where lca(x, y) is x.
However it worked, and after doing some dry runs i understood why it worked but you didnt cover this case in the examples.
Just a positive feedback 😄
Thank you so much! Great explination...
Very nice explanation. Thank you.
After so many days....yayyyy I could solve a ques all on my own and on first try...dayumn..Ik it's not a big deal but it's a good milestone for me
Awesome Explanation! Understood.
crystal clear sir
Really loved the explanation!
One of the best dry run done ever
faadu bhai faadu
Great explanation!
Huge respect...❤👏
The solution was great but I think it wont give right answer if the other node is not in the tree. In that case we have to do brute force only I think.
Edit: I just saw the leetcode question of this video and it was mentioned that it is guaranteed that p and q will be present in the tree.
now i feel confident in trees by watchng this tree series.
Intuition:
Consider a node as a potential answer (LCA). If both left and right subtrees return non-null values, it means both nodes p and q have been found in different subtrees, confirming that this node is indeed the LCA.
Now, consider a node that is not the answer. In this case, either the left or right subtree (or both) will return null. However, if one of them is not null, it indicates that one of the nodes (p or q) has been found, and this information will be passed up the tree to potentially contribute to identifying the LCA at a higher level.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root.val==p.val || root.val==q.val){
return root;
}
TreeNode left= lowestCommonAncestor(root.left,p,q);
TreeNode right= lowestCommonAncestor(root.right,p,q);
if(left != null & right != null){
return root;
}
return left != null?left:right;
}
}
To save people time, In this video he only explained one case where you will get one element in left side and one in right. but there are also some cases, Consider that we have both the elements in left side of subtree? or there is no element present etc. So this is not the video I was looking for I like to understand every possible case.
It will consider the case in which both the nodes are there on the left or right side of the tree. Look at the base condition.
// Code For Naive Solution
class Solution {
bool getPath(TreeNode* root, TreeNode* x, vector &path) {
if (root == NULL) return false;
path.push_back(root);
if(root == x) return true;
if (getPath(root->left, x, path) || getPath(root->right, x, path))
return true;
path.pop_back();
return false;
}
vector getPathtoNode(TreeNode* A, TreeNode* B) {
vector path;
if (A == NULL) return path;
getPath(A, B, path);
return path;
}
TreeNode* findLastCommon(vector a,vector b){
TreeNode *lastCommon=NULL;
for(int i=0;i
Love This solution
Thansk a lot for both approaches.............Most of us think that ....what if p and q both on the same path then ?... Like if p and q on the same path then, first whether p or q meet on that path and return that and no need to go further onthat path and all other root will then return null ...SO as Striver said, if either of null then we return value part.. so we got answer in this case too.
Can there will be a duplicate node too @striver?
What if node 7 was the left node of node 8 ? @ 10:00
If you got 7 you return
As soon as node 8 is encountered, it returns its value to the parent node and we don't even need to check for 7 bcoz in that case 7 will lie in the subtree rooted at node 8.
We learn from u bhaiya♥️
how many more videos left in tree series?
Eagerly waiting for DP series.
Just sooo good
Thank you! 😇
very nicely explained
what an explanation 🙌
Looking at comments I think I am the only one who got another idea apart from this recursive approach. The intuition is to use property of BST. the right of node will contains elements > root and left of nodes will contains elements < root. So you can use this to find the solution iteratively.
its no where written in the question that its a binary search tree
Nice explaination!
I liked this convention more.
if ( left && right) return root;
else if ( left) return left;
else return right;
ohhh bhaiiiiii, behtreeen solution hai
Superb explanation!
Awesome Explaination..
bhaiya just watching 4 min video i got accepted solution in leetcode simply hatsoff bhaiya i dont even think i can solve this question
but why don't we return or break the program as soon as we get lca for two nodes
Understood sir❤🙇♂🙏
Beautiful Explanation 😍😍
Hi Striver, I think in the brute force technique the space complexity is O(Height of the tree) am i right ?
thanks man .... God bless you
thank you , you helped a lot
You are rock bhaia Jee