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

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.

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

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.

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

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!

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

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

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.

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

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

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.

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

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

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

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

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.

Thanks a lot. Working on my recursion.

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

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

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

Great Explanation :) Appreciate your hard work !!!

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

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.

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

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

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

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

Excellent explanation regarding the recursive call!

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

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

Best video. Thanks a lot!

This way of showing and explaining code is really great👍

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

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

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

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

Loved the thinking behind it

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

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?

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

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.

Thank you so much 🧡

extremely helpful!!!

Great explanation. Thanks a ton man!

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

love it !!!!!!!!! Great Expl..

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

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.

Dude, You just made it so easy.

Great explaination !!

You are really great!

great explanation! keep up the good work

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

Great explanation!

Great job!

You make it sooo easy.

Thank you!

thanks!!

wow you're an excellent teacher!

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!

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?

Thank you so much

Thank u buddy☺️ u r amazing

love your videos bro!

The best teacher out there :D

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.

Awesome, thank u for rich content

Amazing explanation:)

干的漂亮！ Great explanation! Thank you!

Elegant Explanation

Awesome!!!!

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

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

Very good explanation

thanks man! you are awesome

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

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!

You're Goated!

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!

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

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.

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?

Genius!!!!

Phenomenal

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

Hi there! is the code still in the description?

You’re the best

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

Good channel

had this on an exam recently lol thx

really clean solution code

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

great explenation where is the code ?

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 :)

Could you explain how can we do it for a graph or a n-ary tree. Thanks

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)

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

You think like my mind ☺

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

lol, the little ohmitofo at the end