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 UA-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.
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.
2nd Example from 9:15 --------------------------- Here's my detailed analysis of this question: garmadon.notion.site/Lowest-Common-Ancestor-536c297563214568b36674a1b3ce7a83
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.
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.
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.
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.
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 😄
@@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?
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?
Python code: class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root or root==p or root==q: return root l=self.lowestCommonAncestor(root.left,p,q) r=self.lowestCommonAncestor(root.right,p,q) if not l: return r if not r: return l return root
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.
In this question, we are guaranteed to find p and q as per the problem statement. One interesting follow up question is : return null if either p or q or both are not present in the tree. Hint : solve it using a Post Order traversal.
EXPLAINATION The question is simply asking to find the subtree's root which will contain both n1 and n2, right?! So we do the same, **1 -Well, if there is no root, you gotta return null/root. if(root==nullptr) { return root; }** **2- if your root data contains either n1 or n2, you return that root. WHY?? Because if the root itself is one of the two nodes, then it itself must be the LCA. Cuz, the other one no matter where, will have lca as the other node, which is now the root** **3 - Now save your Left answer of the left side of tree in a variable, this variable with either have a null or a valid node depending on recursive calls if it finds the required node, Do the same for the Right side make a variable and save the answer.** **4 - Now, we have two different variables namely left and right. Both contains answer either null or a valid node, now we check three conditions** **5- If Left answer is not null and right answer is also not null, then the answer is the root itself, since left and right are subtrees of the root and if both are not null it clearly means the values n1 and n2 lies in right as well as left side, For example, Example test case 1 is the perfect example for this case** **6 - If left answer is not null but right answer is null, then it means both n1 and n2 lies on the left side of tree inside the subtree with root as left answer, return left answer. For example, Example test case 2 is the perfect example for this case** **7 - If right answer is not null but left answer is null, then it means both n1 and n2 lies on the right side of tree inside the subtree with root as right answer, return right answer** **SPOLIER ALERT CODE AHEAD** **SPOLIER ALERT CODE AHEAD** **SPOLIER ALERT CODE AHEAD** **SPOLIER ALERT CODE AHEAD** **SPOLIER ALERT CODE AHEAD** **SPOLIER ALERT CODE AHEAD** **SPOLIER ALERT CODE AHEAD** **SPOLIER ALERT CODE AHEAD** **SPOLIER ALERT CODE AHEAD**
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
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 UA-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
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.
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. 😄
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;
}
}
}
Thanks a lot for contributing to the community.
Nicely understood!!!
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.
best explanation till date!!Vey very very easily understood as a noob coder.Thanks a lot!!
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
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.
i am solving question by myself without watching lec bcoz of youre awosome lectures thank you keep it up!!
Classic binary tree question! Thanks Striver.
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.
Understood,able to solve by brute force and with optimized approach after getting a hint.Thank you striver
Never thought that the solution for this question will be so simple and easy to understand.
Bhai ismei simple kya tha 😢
Such a cool teaching... and an awesome logic.
Wow I was able to write the code myself just after explanation.
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
Nicely explained and easily underatood
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.
the optimized approach was awesome, loves the intuition !!! easyily understood
Simple and lucid explanation. Thanks, bro.
2nd Example from 9:15
---------------------------
Here's my detailed analysis of this question:
garmadon.notion.site/Lowest-Common-Ancestor-536c297563214568b36674a1b3ce7a83
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
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Commenting to increase count +1 , Nice collection of videos.
Striver ,your videos are perfect.
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.
// 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
Overwhelming explanation 👏👏👏👏 bhaiya 🥳🥳🥳
Completed 28/54 (51%) done!!!
u work is really helping us to understand this type of concept. So thank u !!
nice bro keep it up you are our motivation😎😎😎
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;
}
}
tree question are very easy after watching your lecture. thanks bhayia
your on a different level !!! thank you 💎
Next level explaination💯
Great Explanation, loving the series so far
superb explanation!!! it made trees very easy for me. Thank you so much.
Thankyou for amazing solution Striver
too smooth too good...amazing explanation...thank you STRIVER
Thank you so much Striver !
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
thanks bro, your dry run was great,, was struggling to visualize recurssion
you got new subscriber . outstanding explanation !🙂
I liked this convention more.
if ( left && right) return root;
else if ( left) return left;
else return right;
Understood! Super amazing explanation as always, thank you very much!!
great video .... very nicely explained ...... just loved it ❤
Thank you :)))) Was nicely explained.
Crystal clear explanation !!
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.
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.
One of the best dry run done ever
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 😄
Huge respect...❤👏
bhaiya just watching 4 min video i got accepted solution in leetcode simply hatsoff bhaiya i dont even think i can solve this question
now i feel confident in trees by watchng this tree series.
@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?
Very nice explanation. Thank you.
Best ever solution for this problem!
We learn from u bhaiya♥️
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?
Well illustrated. Thanks
Understood sir❤🙇♂🙏
Beautifully explained!!
beautiful explanation my man.
very well explained !! Thanks
Really loved the explanation!
Thank you so much! Great explination...
Python code:
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root==p or root==q:
return root
l=self.lowestCommonAncestor(root.left,p,q)
r=self.lowestCommonAncestor(root.right,p,q)
if not l:
return r
if not r:
return l
return root
Great explanation!
Totally clear, loving this series. Thanks a ton for making this.❤️
Understood ❤
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
Awesome Explanation! Understood.
Awesome Explaination..
very nicely explained
You are so good. Thank you!
ohhh bhaiiiiii, behtreeen solution hai
Bhai tu great h yaar!!! I mean sach me great h yaar
Mzza aa jata h jb koi complicated concept smjh me aa jata h to
this is just perfect
Nice explaination!
faadu bhai faadu
UNDERSTOOD! THANK YOU🙌
how many more videos left in tree series?
Eagerly waiting for DP series.
just saw the half video, and tried my self. and boom i solved it.
completed lecture 27 of Tree Playlist.
thank you , you helped a lot
Beautiful Explanation 😍😍
Superb explanation!
In this question, we are guaranteed to find p and q as per the problem statement.
One interesting follow up question is : return null if either p or q or both are not present in the tree.
Hint : solve it using a Post Order traversal.
Best Explanation Bro Striver Op In the comment guys
thanks man .... God bless you
EXPLAINATION
The question is simply asking to find the subtree's root which will contain both n1 and n2, right?! So we do the same,
**1 -Well, if there is no root, you gotta return null/root. if(root==nullptr) { return root; }**
**2- if your root data contains either n1 or n2, you return that root. WHY?? Because if the root itself is one of the two nodes, then it itself must be the LCA. Cuz, the other one no matter where, will have lca as the other node, which is now the root**
**3 - Now save your Left answer of the left side of tree in a variable, this variable with either have a null or a valid node depending on recursive calls if it finds the required node, Do the same for the Right side make a variable and save the answer.**
**4 - Now, we have two different variables namely left and right. Both contains answer either null or a valid node, now we check three conditions**
**5- If Left answer is not null and right answer is also not null, then the answer is the root itself, since left and right are subtrees of the root and if both are not null it clearly means the values n1 and n2 lies in right as well as left side, For example, Example test case 1 is the perfect example for this case**
**6 - If left answer is not null but right answer is null, then it means both n1 and n2 lies on the left side of tree inside the subtree with root as left answer, return left answer. For example, Example test case 2 is the perfect example for this case**
**7 - If right answer is not null but left answer is null, then it means both n1 and n2 lies on the right side of tree inside the subtree with root as right answer, return right answer**
**SPOLIER ALERT CODE AHEAD**
**SPOLIER ALERT CODE AHEAD**
**SPOLIER ALERT CODE AHEAD**
**SPOLIER ALERT CODE AHEAD**
**SPOLIER ALERT CODE AHEAD**
**SPOLIER ALERT CODE AHEAD**
**SPOLIER ALERT CODE AHEAD**
**SPOLIER ALERT CODE AHEAD**
**SPOLIER ALERT CODE AHEAD**
CODE IMPLEMENTATION
Node* lca(Node* root ,int n1 ,int n2 ) {
if(root==nullptr){
return root;
}
if(root->data==n1 || root->data==n2){
return root;
}
Node* LEFTSIDE =lca(root->left,n1,n2);
Node* RIGHTSIDE =lca(root->right,n1,n2);
if(LEFTSIDE!=nullptr && RIGHTSIDE!=nullptr){
return root;
}
else if(LEFTSIDE!=nullptr){
return LEFTSIDE;
}
else{
return RIGHTSIDE;
}
}
what an explanation 🙌