L27. Lowest Common Ancestor in Binary Tree | LCA | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@rahulsrivastava1040]

Understooooooooooooooood :) and done everything thank u so much striver :)

[@dipeshsaili4468]

Do TreeNode* left and right take space? I mean definitely there's pointer to heap/ dynamically

[@gshreyaa]

Will this approach work if numbers are not present in the tree?

[@vivekparashar...8716]

done bro

[@ToonTorque]

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

[@sleepypanda7172]

Every other KZbinr 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.

[@human75788]

I watched about 4 minutes of your video and coded it myself.. Your explanation is just heaven .

[@als_venky7057]

but the real part starts after 4minutes😂

[@nishankjain88]

@@als_venky7057 😂😂

[@rohanverma3111]

@@als_venky7057 xD 😂😂😂😂

[@only_for_fun1234r]

@@als_venky7057 😅😅

[@SlapB0X]

that approach should not be done.. watch the latter half for the optimal approach

[@vishalgowrav]

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; } } }

[@surajpalsau870]

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🤠

[@dikshasoni52a98]

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 ......

[@samsingh43]

@@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

[@imranimmu4714]

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.

[@RahulPatel-hr4qe]

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

[@tanyagupta4247]

I tried to understand the logic by myself for 2 times and then coded it without seeing anyone's code. Feeling so good💗

[@electronx5594]

heyy same, but why are you here then🤔

[@parthsalat]

@@electronx5594 Just to comment this. 😄

[@ayush52905]

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.

[@vinaygupta2369]

Striver bhai rocked.. buddy you are helping thousands of folks like me preparing for DSA interview. :)

[@_who__knows__16]

Thanks a lot for contributing to the community. Nicely understood!!!

[@nikhilnagrale]

// 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

[@parul8334]

Love This solution

[@giridharjadala2182]

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.

[@rushidesai2836]

Classic binary tree question! Thanks Striver.

[@mukitmahmudul2616]

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.

[@349_rahulbhattacharya6]

best explanation till date!!Vey very very easily understood as a noob coder.Thanks a lot!!

[@kartiksaini5619]

The best explantion 🔥🔥🔥🏅 really loved it🔥🔥I must say this is your best video

[@knowthrvdo]

i am solving question by myself without watching lec bcoz of youre awosome lectures thank you keep it up!!

[@nelsonoboo5423]

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

[@rishabhgupta9846]

Understood,able to solve by brute force and with optimized approach after getting a hint.Thank you striver

[@HoneyComb1711]

Thank you very much! Striver is the best channel! I refer only to striver videos!

[@jajateenandineesahoo259]

Never thought that the solution for this question will be so simple and easy to understand.

[@170_akashgupta_cse2]

Bhai ismei simple kya tha 😢

[@harishsn4866]

Simple and lucid explanation. Thanks, bro.

[@surendradas8174]

Wow I was able to write the code myself just after explanation.

[@manasdeora4601]

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.

[@neelpatel122]

Explanation is flawless. keep it up.

[@ManojKumar-jb4sc]

Nicely explained and easily underatood

[@thegreekgoat98]

Such a cool teaching... and an awesome logic.

[@stith_pragya]

Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@ritikshandilya7075]

Thankyou for amazing solution Striver

[@abhaykumarsingh3884]

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; } }

[@ishangujarathi10]

the optimized approach was awesome, loves the intuition !!! easyily understood

[@chrisogonas]

Well illustrated. Thanks

[@Mayanksingh-qp6dy]

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.

[@sonukumarpandit9731]

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.

[@lifehustlers164]

Completed 28/54 (51%) done!!!

[@mohit7717]

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?

[@ayushpatel2171]

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.

[@apmotivationakashparmar722]

Thank you so much Striver !

[@charlesbabbage6786]

Beautifully explained!!

[@BTECSPRAKASHSINGH]

Striver ,your videos are perfect.

[@friendsav1244]

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.

[@echocoding4550]

u work is really helping us to understand this type of concept. So thank u !!

[@snehabaser3155]

Next level explaination💯

[@droid-aman]

thanks bro, your dry run was great,, was struggling to visualize recurssion

[@prabhakaran5542]

Understood ❤

[@manojjain3501]

Commenting to increase count +1 , Nice collection of videos.

[@jayantmishra6897]

tree question are very easy after watching your lecture. thanks bhayia

[@dipeshsingh2112]

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.

[@vvvvvviiii]

its no where written in the question that its a binary search tree

[@uRamPlus]

your on a different level !!! thank you 💎

[@soumalyadhar.28]

too smooth too good...amazing explanation...thank you STRIVER

[@OIAOa]

crystal clear sir

[@devanshubilthare5277]

Great Explanation, loving the series so far

[@_CodeLifeChronicles_]

this is just perfect

[@harshit4190]

how many more videos left in tree series? Eagerly waiting for DP series.

[@rakshayadav1892]

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

[@roshnisingh7364]

very well explained !! Thanks

[@darkexodus6404]

I liked this convention more. if ( left && right) return root; else if ( left) return left; else return right;

[@VijayKumar-j4m1b]

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

[@mounishgoud8417]

Crystal clear explanation !!

[@dpxy1599]

faadu bhai faadu

[@pragyapal4258]

superb explanation!!! it made trees very easy for me. Thank you so much.

[@sakshisrivastava4265]

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

[@rekhaagarwal7224]

One of the best dry run done ever

[@MohdMasood-p7n]

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 😄

[@priyanshpatel2078]

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; } }

[@aadeshsharma0001]

now i feel confident in trees by watchng this tree series.

[@jinhuang7258]

You are so good. Thank you!

[@cinime]

Understood! Super amazing explanation as always, thank you very much!!

[@DeadPoolx1712]

UNDERSTOOD;

[@vinayjadon7840]

@10:08 you returned when you found 8, but what if 7 is present in 8's subtree, that is not explored?

[@takeUforward]

Then 8 will only be the lca na even if 7 is under subtree. So why to go deep

[@renukasubramaniyam754]

What if 7 is not present in the tree at all

[@vinayjadon7840]

@@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.

[@your_name96]

@@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?

[@2xReturns-FOOTBALL]

beautiful explanation my man.

[@rushyya]

UNDERSTOOD! THANK YOU🙌

[@ayushpatel4475]

Overwhelming explanation 👏👏👏👏 bhaiya 🥳🥳🥳

[@shivalikagupta3433]

Thank you :)))) Was nicely explained.

[@prachimatta]

Excellent

[@vivekveman4961]

Best ever solution for this problem!

[@nilanjanmajumder8508]

great video .... very nicely explained ...... just loved it ❤

[@rashikakurhade3499]

Very nice explanation. Thank you.

[@SnehithYamalapalli]

Just sooo good

[@abc-ym4zs]

bhaiya just watching 4 min video i got accepted solution in leetcode simply hatsoff bhaiya i dont even think i can solve this question

[@vivekparashar...8716]

nice bro keep it up you are our motivation😎😎😎

[@adrishbhattacharya508]

Great explanation!

[@amsuprith]

Thank you so much! Great explination...

[@rajakunalpandit3594]

what will happen in the case of skew tree? What if a node doesn't have it's left node and it's right node is the required node and the node itself is the required node. Then how this solution work in that case?

[@MohanaKrishnaVH]

Awesome Explanation! Understood.

[@nagavedareddy5891]

Huge respect...❤👏

[@SagarSundriyal]

good one

[@14-a-akritiawasthi35]

We learn from u bhaiya♥️

[@shashikantmony7844]

Really loved the explanation!

[@johncenakiwi]

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.

[@amarpreetkaurrekhi71]

very nicely explained

[@Shivi32590]

thank you

[@sushmitakumari8252]

you got new subscriber . outstanding explanation !🙂

[@iamnottech8918]

wow !!

[@himanshidafouty347]

Understood

[@fazilshafi8083]

Thank you! 😇

[@mriduljain1981]

completed lecture 27 of Tree Playlist.

[@aryansinha1818]

It feels like I am sitting in my super confident English teacher class.

[@aswithasai4015]

what if the p is a root and q is a node in the branch of p

[@lakshsinghania]

brute force code : /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector getPath(TreeNode* node, TreeNode* targetNode, vector& arr) { if (!node) return {}; arr.push_back(node->val); if (node->val == targetNode->val) return arr; vector leftPath = getPath(node->left, targetNode, arr); if (!leftPath.empty()) return leftPath; vector rightPath = getPath(node->right, targetNode, arr); if (!rightPath.empty()) return rightPath; arr.pop_back(); return {}; } int lca(vector& pathP, vector& pathQ) { int lowestCommon = 0; for (int i = 0; i < min(pathP.size(), pathQ.size()); i++) { if (pathP[i] == pathQ[i]) lowestCommon = pathP[i]; } return lowestCommon; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL) return nullptr; vector pathP, pathQ; pathP = getPath(root, p, pathP); pathQ = getPath(root, q, pathQ); int outputNode = lca(pathP, pathQ); TreeNode* resultNode = new TreeNode(outputNode); return resultNode; } }; understood this approach pretty well as got help from prev video