Lowest Common Ancestor Between 2 Binary Tree Nodes (A Recursive Approach)

[@BackToBackSWE]

Table of Contents: The Problem Introduction 0:00 - 0:33 Getting Good At Tree/Recursive Problems 0:49 - 2:51 What We Will Learn In This Video 2:51 - 3:34 Case #1: The Common Case 3:34 - 5:27 Case #2: The Overlap Case 5:27 - 6:47 The Key To Recursion. Reduction To A Single Focus. 6:47 - 7:55 Defining Our Recursive "Policy" At A Single Node 7:55 - 9:15 Policy #1: Both Found 9:15 - 9:32 Policy #2: Either Found (but not both) 10:48 - 12:51 Live Code Run-through 12:51 - 16:05 Time Complexity 16:05 - 17:15 Space Complexity 17:15 - 18:50 Wrap Up 18:50 - 20:10 Mistakes: 9:34 -> I meant "if we find x on the right", not "if we find x on the left" 16:35 -> We don't have a "potential" to touch the whole tree, we will touch the whole tree with this approach. Even if the LCA is found in say...the left subtree of a node...it will still make an LCA call to its right and of course get 'null' back since both nodes were already found in the left subtree and an LCA was already reaped. Before You Say It: For the 2nd base case we do value comparisons and this can present a problem if the value at a node we are searching for is repeated in the tree. This can simply be converted into a reference check since in the problem (at the time this video was made) passes us the reference to the 2 nodes we are searching for an LCA for. References in memory will always be unique per node. The code for this approach to the LCA problem as applied to Binary Trees is in the description. Fully commented for teaching purposes.

[@huynhduc9]

Hi man, where is the code? It's not in the description.

[@laurakraman2737]

You make me feel normal. That's a compliment. All week I've been feeling like I'm never gonna get it.

[@BackToBackSWE]

You are normal. These problems just suck. Stick with it. If I can do this, anyone can.

[@philipdimeski5188]

Glad I'm not the only one!

[@GvSharmaBKP]

This guy is really kind

[@ajayunni6361]

I just want to say that your videos has actually helped me immensely especially solving tree problems. Your approach of taking a tree problem and then thinking it based on one single node is priceless. A thousand thanks to you man! Today I landed my dream job! Anyone who is reading this, do watch all his videos, they are awesome.

[@BackToBackSWE]

Oh nice!!! Glad you are happy. Wish you the best - your internet friend Ben

[@BharCode09]

Before one understands Recursion, one must first understand Recursion! I know, that's a joke, but it hurts.... Very bad.. Very deep!

[@BackToBackSWE]

ye

[@_sudipidus_]

Your joke overflows.. :P Improved version:=> Before one understands recursion one must first understand recursion until he or she understands recursion :)

[@amitbajpai6265]

Sorry but maximum recursion limit has been reached .

[@wearegeeks]

Those few words of the beginning. Thank you man, I'm still struggling with most of the problems I encounter. I thought I was stupid or something.

[@adityasrivastava7956]

hola bro wassup

[@sheepycultist]

Thank you! I solved this initially using two stacks, but the runtime was pretty abysmal. This makes the optimal solution much more clear!

[@BackToBackSWE]

nice

[@abdullahzaidan7394]

it looks like you have spend a lot of time going deep into the concepts to make these type of problems easy for us. Thanks for such hard work. Hope your content gets more views.

[@BackToBackSWE]

thanks for watching

[@deepaksarvepalli2344]

you gave me a chance to make myself better than yesterday...

[@PritamBanerjee999]

This is the best explanation I have found for this problem in the internet. Thank you

[@ekejma]

He helps you to deeply understand the problem deeply. Very grateful to break up study sessions with his lectures.

[@chhaviagarwal7514]

The way you explained each and every thing related to a problem is just amazing

[@BackToBackSWE]

thanks

[@akshitarora470]

This was a great explanation. I have been watching all your videos, a couple of them every day, coding them out later, and trying to make myself good enough for constructing a logical thinking for these interview questions. No tutor on internet teaches via giving the intuitive approach, and that is what sets you apart, and makes you stand out! You really do a wonderful job! Thanks a lot!

[@BackToBackSWE]

great good luck

[@prithazz]

This is the best video on recursion I have watched. Still not able to fully apply recursion to other problems but this makes a lot of sense how to "read" the function when the results from bottom come up and hit base.

[@BackToBackSWE]

Nice and it just takes time.

[@alammahtab08]

Great explanation, some important things that I think are worth mentioning here. I think the implementation is actually a bit wrong. For example for the below binary tree, lets say we want to find out the LCA of nodes 5 and 6. With the implementation shown in this video, the left recursive call will satisfy the base case at node 5, because node 5's value matches, so it will return the Node 5 without trying to find the match for Node 6 in the left subtree. 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 So to really start the evaluation from bottom of the tree to top, the recursive calls should be done first, before checking the Node's value. Below is the implementation : /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; TreeNode leftSearchResult = lowestCommonAncestor(root.left, p, q); TreeNode rightSearchResult = lowestCommonAncestor(root.right, p, q); if (root.val == p.val || root.val == q.val) return root; if(leftSearchResult != null && rightSearchResult!= null ) return root; return leftSearchResult != null? leftSearchResult : rightSearchResult; } } The leetcode question guarantees that both nodes p and q will always exist in the binary tree. But If only one node exist in the tree then above implementation will return the node that matched the value in the binary tree. Which is kind of wrong, ideally it should have returned null because we were not able to find both the nodes in the tree. =============== Follow up question ========= What if we are not guaranteed that both nodes p and q will exist in the binary tree? Approach : We are going to take two boolean properties firstNodeExist and secondNodeExist, and when we find that first or the second node exist in the binary tree, we will set the appropriate boolean property to true. This way we can find out whether both the values exist in the tree or not, and if both the values are not found in the binary tree we return null as LCA from the lowestCommonAncestor method. Implementation : class Solution { public boolean firstNodeExist; public boolean secondNodeExist; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; TreeNode lca = lca(root, p, q); return (firstNodeExist && secondNodeExist)? lca : null; } public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; TreeNode leftSearchResult = lca(root.left, p, q); TreeNode rightSearchResult = lca(root.right, p, q); if (root.val == p.val) { firstNodeExist = true; return root; } else if(root.val == q.val) { secondNodeExist = true; return root; } if(leftSearchResult != null && rightSearchResult!= null ) return root; return leftSearchResult != null? leftSearchResult : rightSearchResult; } } I made some notes here github.com/eMahtab/lowest-common-ancestor-of-a-binary-tree , you might find it helpful.

[@BackToBackSWE]

thx

[@kirancoding1576]

Am very scared looking at problem on trees and graphs but your explanation is making me understand them easily . thank you for all the videos on trees

[@BackToBackSWE]

Give it time, they get easy

[@aidardarmesh8024]

Best explanation and great advices not from senior-shmenior, but for usual human and in human language. Thanks!

[@BackToBackSWE]

sure

[@blatogh1277]

This videos is really helping to understand how this LCA works. The basic idea is first to find out is where are those two nodes are and second do the return and determining whether is common ancestor

[@manogyapulivendala2504]

Damn, this is THE VIDEO to watch when you're starting out with Recursion and Trees. You're awesome man!

[@BackToBackSWE]

ye

[@pyak6761]

you will be a big reason why i get a job at the big boys in six months if i make it. bro this content is so gooooold cause you actually break it down. i don't even need to see the code cause the concepts are so good dam

[@BackToBackSWE]

great - live a good life

[@user-ov5nd1fb7s]

Another easier to understand algorithm is: 1. find both nodes while counting the depth for each 2. if one of the nodes is deeper than the other, bring that variable up to reach the same depth as the other 3. now both are on the same depth. Bring both of them up 1 node at a time until they point to the same node. This requires node to have a pointer to its parent though

[@DavisBelisle]

This is the best video about trees I have ever seen. Thank you so much!

[@tathagatnegi5923]

This way of showing and explaining code is really great👍

[@BackToBackSWE]

great

[@SelftaughtSoftwareEngineer]

I really liked that you include the code and walk us through it in this video. Thank you for sharing!

[@BackToBackSWE]

sure

[@AshokBathini]

Great explanation & cool algo. There's a minor bug: If only one of the values (x or y) is present in the tree, instead of returning NULL, it returns the Node that contains the value x or y as the LCA.

[@BackToBackSWE]

The problem assumes both nodes are present

[@aamirjamal6833]

There is no chance that I would be able to think this out in an interview by myself. Anyways, thanks for the lucid explanation.

[@BackToBackSWE]

yeah, me neither

[@aakashjain3498]

Saw you're linkedin. Can't believe you doing so much only when you're 21.

[@BackToBackSWE]

I'm 20 rn and nah, it is nothing. Anyone can do anything whenever (within biological, physics, & genetic constraints).

[@josephgodwin8729]

This is the best video on trees and recursion! on my way to solve all Tree questions on LC -->

[@rajatsaxena2647]

Thanks a lot for these detailed videos. How about the approach where you walk up the tree until you hit the root, for both nodes and create two arrays containing parents of the nodes. Then we can run a loop and keep on matching the parents from both these arrays and return when we’ve found a difference. That would represent the lowest common ancestor in my opinion.

[@BackToBackSWE]

Yes. I'm familiar with this approach. We would need parent pointers for that.

[@idemchenko-js]

Thank you for your great explanation. Awesome that you mentioned about focusing on a node. Imho, it is a bit clearer with languages that support sum types and pattern matching as you simply list all possible variants. However, I believe, the key question is still open. Why did you do `if (leftSearchRes == null) return rightSearchRes; if (rightSearchRes == null) return leftSearchRes;`. Everything else makes sense, but this is a key twist to the whole problem, I assume.

[@BackToBackSWE]

If both are null then the latter if statement still returns null for the search. Otherwise, it is a matter of passing up the result from a single successful subtree search.

[@sui8261]

Very clear, Nice job! Why there are so many guys on KZbin can teach better than college professors...

[@BackToBackSWE]

Hahaha, maybe we are college professors in disguise 👀👀🕵🕵 But in all seriousness, a student is better positioned to teach concepts to other students than a seasoned professor is because a student knows exactly how other students will get stuck. Aka...most esteemed professors do research and are very, very, brilliant. Much more than any outsider could comprehend. But...there is a coefficient of loss that teaching introduces to that intellect. A perfect lesson builds a perfect bridge from the student's current level of understanding, to the teacher's understanding. So for me...I'm not that smart, I'm not the best problem solver...but I can angle lessons in a way that will bring anyone into my mind and way of thinking better because I had to cross that bridge only 1 or 2 years ago. Many professors and teachers crossed their bridge 10's of years ago and they lose that connection to the student's plight. Long story short...teaching is a whole different skill and a hard one to get right. Regardless, I have the utmost respect for all those who have every taught me (both terrible and brilliant). It is the nature of things that make it this way. Very very very very hard to get right. Afterward: Dang...this is a wise comment I think...something I'd read on Reddit in retrospect.

[@sui8261]

@@BackToBackSWE Agreed, that make sense. Anyways, I was confused about LRU cache implementation and LCA for a long time but fortunately I saw your video in my recommendation list today and I can now finally understand them...Thank you for your hard work and keep going!!

[@BackToBackSWE]

@@sui8261 Will do

[@rishabhkukreja3485]

I finally understood the key behind solving recursive problems. Thank you!

[@BackToBackSWE]

nice.

[@mrallenchuang]

Keep it up, been watching you for over a month and already feel like i've learned so much!

[@BackToBackSWE]

nice

[@sammynochains3455]

Finalllllly .. a good video .. after searching recursively for 2 hrs.. 😁😁

[@BackToBackSWE]

nice

[@jonch009]

The way you explain concepts is exceptional! Keep up the great work!

[@BackToBackSWE]

thanks

[@Piyushraj0]

Loved the thinking behind it

[@sher.5027]

Dude, You just made it so easy.

[@rajatsemwal1865]

Who are you, who are you so wise, in the ways of Computer Science? Well, memes apart, your explanation was really on point and easily understandable for a non-pro coder like me. I also get confuse and scared of recursion and tree problems. Thank you! All the best and stay safe!

[@BackToBackSWE]

thx and thx

[@b9944236]

I think the beginning talk is more precious than how to solve this problem.

[@SuperMehroze]

One thing I noticed is that this code actually works for both BST and BT.

[@lakshmimanasamvs7833]

thank you so much!! I finally understood this after watching your video. I was struggling to understand this before watching your video.

[@BackToBackSWE]

great

[@saptarshiganguly1683]

Please keep making such videos more. It's really helpful.

[@hooshmandali]

Thanks for the great video. I think there is a typo in function names. The initial name is "lca", however in recursive calls, "search" function is called. One of them should be changed to match the other one. Again awesome job and good luck!

[@BackToBackSWE]

yeah noted, thanks

[@fayel.8911]

Thank you so much for sharing. Is that possible we can see you solve LCA similar questions on Leetcode and compare what difference between all to them?

[@marcusrobinson5516]

Thanks for this video man, getting me to try and understand recursion a little better at least

[@BackToBackSWE]

nice

[@amangoyal3583]

Can u please tell why we return the left root if right is not having any node or we return right node if left is not having any node? 12:25

[@vedantiyangar151]

I encountered this problem for the first time in an interview for one of the Big Four. My dumb ass maintained an array of the references of the parents of each node to be found and compared the references to find a common point. No wonder they kicked me out. :(. Thanks to Ben, I will get MY REVENGE.

[@BackToBackSWE]

hahahahaha

[@SunkuSai]

Why is this a terrible solution? The time complexity is the same because each node is visited at most twice. The space complexity is O(n) instead of O(h) which is much worse for a balanced tree. But it's still a reasonable solution, right?

[@vedantiyangar151]

@@SunkuSai I agree, but I believe the other interviewees came up with this solution, and the interviewers had a limit or something.

[@notyournormaldev1419]

@@SunkuSai can you explain more about your approach 🙏 which array you are talking about

[@nicesacbro4891]

​@@notyournormaldev1419 search for x , and store its path in an array. Do the same for y. Now start comparing those arrays, when you encounter different values at an index, the index before that stores the LCA.

[@anmolmishra1914]

Thanks a lot. Working on my recursion.

[@BackToBackSWE]

nice

[@trushapatel9012]

Your explanations are very good. Thanks! Preparing for Amazon On Site Interview from here.

[@BackToBackSWE]

nice, good luck

[@danni6113]

Excellent explanation regarding the recursive call!

[@BackToBackSWE]

thx

[@darod6098]

You're the best explaining. It's amazing.

[@BackToBackSWE]

no u

[@antonbohomol380]

I didn't get where is the code you are referring to. The description contains only the explanation.

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@antonbohomol380]

@@BackToBackSWE Got it, thanks!

[@peanutbuttermochi9499]

minor typo i believe. you say TreeNode leftSearchResult = search(root.left,x,y) but your function is called lca, not search.

[@harsha20jun]

Great explanation. I really admire your videos. Got a question though. This algorithm assumes both the nodes we are finding exist in the tree somewhere. How would the algorithm change if we are not sure whether both of those exist in the tree?

[@BackToBackSWE]

I'm not sure, would have to think on this.

[@Mrswapsam13]

Great Explanation! Just had a doubt, shouldn't the search be the same recursive function? That is, search(root.left,x,y) should be a recursive call to lca(root.left,x,y)

[@BackToBackSWE]

I don't remember the code presented in this video.

[@taritgoswami3957]

Great! sometimes you become too much abstract to understand. Please try to show at least one example with pseudo-code about which you are talking. Writing down the pseudo-code will help us to better understand. Thanks, keep making this type of videos :)

[@BackToBackSWE]

ok

[@wishingbottle]

love the whiteboard approach (for interviewing), thanks so much!

[@BackToBackSWE]

sure

[@jacariboboye]

Great explanation! Thank you. Best of luck with your internship.

[@BackToBackSWE]

thanks

[@roliverma4483]

The best teacher out there :D

[@arnabbiswas2773]

Hey Benyam! Thanks a lot for this great explanation. I had some doubts regarding LCA but its all gone now. I just noticed a little typo in the pseudocode that you showed (the function name is lca() but you call search() for the leftSearchResult and rightSearchResult). Apart from that the video and the explanation were super easy to understand! Thank a lot!

[@BackToBackSWE]

I would look into this but too busy. Just want you to know I saw this and can't respond

[@arnabbiswas2773]

@@BackToBackSWE Well it's just a small typo. Moreover you already have the correct code in GitHub.

[@BackToBackSWE]

@@arnabbiswas2773 ok

[@soojinlee2420]

Thank you soooo much for the video, You explanation is really clear and intuitive :) If you looking for next subject for a video, can you do minimax? Me and my friend have a hard time to understand the minimax u.u

[@BackToBackSWE]

maybe, I only take requests of Patrons for now to be fair to those supporting the project

[@umapathybabu8397]

Helped a lot, can you do some oo design questions?

[@BackToBackSWE]

yeah

[@supreethr6269]

Just have a small suggestion. In the algorithm , I got confused as you have mentioned 'search(root.left,p,q)' instead of lca(root.left,p,q);

[@BackToBackSWE]

ok

[@ayushmishra3388]

Hey this algorithm will only work for non duplicates values of the nodes whose LCA is to be find out? am i correct? wht i mean is lets suppose i am finding LCA for 5, 2. And i find multiple occurrences of 5 and 2, then this algo wont work right?

[@jyotisingh8183]

Where is the code(link) in description? Kindly let me know. Please provide the link. Thank you.

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now

[@ShubhamSingh-cc1bb]

Elegant Explanation

[@BackToBackSWE]

thx

[@fares.abuali]

Thank you so much 🧡

[@adityasrivastava7956]

Best video. Thanks a lot!

[@nclarin1]

Will your solution work on this tree? Because I don't think it will. It will return 4 instead of null? Lca(3, 4, 5) 3 \ 4 \ 6

[@BackToBackSWE]

I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.

[@cacjad]

What i don't understand is that if we arrive at a node with either value p or q, why do we return it immediatley, because isn't it possible that the other node value is further down the subtree?

[@mr_phamtastic]

wow you're an excellent teacher!

[@amitrk23]

Great explanation. Thanks a ton man!

[@kedimnvfjnnvfjffurju]

Very good explanation

[@arielazoulay6553]

great explenation where is the code ?

[@Quintenkonijn]

With the function search(root, x, y) you are referring to lca(root, x, y), right?

[@BackToBackSWE]

yeah, it is just a name change. You are basically searching for occurrences of either x's val or y's val and bubbling up the appropriate result.

[@Quintenkonijn]

Great! Thanks for getting back so quickly. Keep up the great videos like this one and I'm sure you will reach your goal before you know! Cheers :-) @@BackToBackSWE

[@BackToBackSWE]

@@Quintenkonijn cheers

[@IkeVictor]

the recursive functions dont match the function names (lca vs search) a bit confusing but still got the gist of it

[@dingding2779]

I recommend someone with the basics to start watching from the 13th minute.

[@fables5091]

quick question, would we not return lca(root.right) and lca(root.left) as the function given isnt recursive

[@mikedelta658]

Great explanation!

[@digital2man]

You make it sooo easy.

[@edwinrosemond989]

Hi there! is the code still in the description?

[@arnobchowdhury1804]

How much time does one tree recursion problem of medium level should take?Do you always came up with with your own solutions or you took ideas from other solutions?

[@BackToBackSWE]

not sure. And it is a mix, some I write and some I find and try to explain as well as I can

[@JordanHeath745]

Are the steps introduced at 14:00 supposed to be TreeNode leftSearchResult = lca(root.left, x, y) TreeNoderightSearchResult = lca(root.left, x, y) or is search() a completely different algorithm

[@BackToBackSWE]

not sure, I did this video a while back

[@Gavy093]

Will this still work if one of the nodes that we are looking for is not present in the tree?

[@coolnikrox92]

Hey Nice explanation :). Could you make a video on Tries data structure and Segment Tree. Thanks :)

[@BackToBackSWE]

I may but I only now take video suggestions from Patrons to be fair to the people monetarily supporting the project

[@neharikakhera6411]

Great explaination !!

[@BackToBackSWE]

thanks

[@marcuskoay6966]

This is assuming that nodes x and y will always be in the tree right? Does the algorithm you built consider cases where only one of x or y is on the tree?

[@BackToBackSWE]

x and y can be anywhere

[@marcuskoay6966]

@@BackToBackSWE so that means x and y MUST be on the tree right

[@BackToBackSWE]

@@marcuskoay6966 yes

[@gxyxy1012]

had this on an exam recently lol thx

[@BackToBackSWE]

nice

[@dephc0n1]

Same for an interview. But worded different so realizing it's a lca is a major key.

[@chaitanyakumar9229]

GOD level explanation

[@Ashish.Shukla9]

one doubt i think answer will not be null if either of the 2 nodes is not present in our tree....or are we assuming that both nodes are in the tree????

[@BackToBackSWE]

It is guaranteed that both are in the tree

[@arnobchowdhury1804]

your marker was dangerously close to your white t-shirt!

[@BackToBackSWE]

yes, I apologize.

[@rihabtlili7875]

Thank you for this video! But there is something I did not understand. When I tried executing the program manually I noticed that we have to add this condition if (rightSearchResult==null && leftSearchResult==null) return null; Am I right?

[@BackToBackSWE]

I don't remember, I did this long ago

[@peanutbuttermochi9499]

that would be assuming one of the nodes isn't present. I believe in this case we assume the nodes we're looking for are in the tree.

[@vanyastaleva415]

Brilliant! Thank you! In hakkerrank this is marked as an easy task but I don't think it is. I think it's medium.

[@BackToBackSWE]

thanks.

[@CactusFF-d1x]

If you rename the function from "search" to "isCommonRoot", the code would be more obvious.

[@darod6098]

I know that this is 100% stupid, but I had a hard time figuring out why if (leftSearchResult == null) return rightSearchResult; if (rightSearchResult == null) return leftSearchResult; Then I realized that it is the same as the following SUPER UGLY code: if (leftSearch == null) { if (rightSearch == null) { return null; } else { return rightSearch; } } if (rightSearch == null) { if (leftSearch == null) { return null; } else { return leftSearch; } } Super super ugly, but i dont know why i did not understand it until I wrote that. Maybe it helps someone that is kind of dumb like me!

[@BackToBackSWE]

Nothing is stupid. You understood that because it is the literal transcription of the logic.

[@nupurkohli4634]

great explanation! keep up the good work

[@BackToBackSWE]

thx

[@sijiewu]

干的漂亮！ Great explanation! Thank you!

[@BackToBackSWE]

sure

[@TheDEMMX]

really clean solution code

[@BackToBackSWE]

ye

[@TheDEMMX]

@@BackToBackSWE Seriously, I have need researching various ways to solve LCA, this is by far the most elegant code. I noticed some of your solutions are from EPI, but EPI has a different recursive solution for this and the one you explain I love a lot more. Thanks!

[@BackToBackSWE]

@@TheDEMMX great

[@solletisuresh4277]

Awesome, thank u for rich content

[@BackToBackSWE]

Sure

[@raafiulhossain253]

def par(node,parent=None): if node: node.par=parent par(node.right,node) par(node.left,node) def LCA(node1,node2): if node1==node2: #node1 and node2 can be directly child parent return node1 if node1.par==node2: return node2 if node2.par==node1: # ELse the first time the parents are equal, this is the LCA return node1 else: LCA(node1.par,node2.par) Would something like this work?

[@gkprasad100]

How do handle case where X and Y are not present in the tree

[@BackToBackSWE]

If both are not present then null will be returned, this is already handled. The null base case would be the only one hit and all results coming back up the tree would be null thus returning null at the top call