LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]

In this video we'll be solving a popular Facebook interview question: Lowest Common Ancestor of a Binary Tree III. This problem has two solutions, one being quite easy to derive and the other is one of those "ah-ha" trick solutions that you need to have seen before to know off the bat. But once you've seen it, the solution is so elegant that it will blow your mind and is the most optimal way to solve this particular question.

[@veluchamy-zt7gd]

Man, honestly it is one of the underrated channel. Your explanation is crystal clear, easy to understand. I had difficulty in understanding complex problem's solutions, but your videos really helped me. Thanks a lot :)

[@hemmy123]

The two pointer approach took me a while to understand but I think this rephrasing might help a few people. As mentioned in the video, P_copy takes 3 steps and Q_copy takes 2 steps. This results in a difference of 1 step which is not what we want. What we need to do is essentially make them do the same amount of work so we arrive at the same node. What we can do is combine them, so P_copy and Q_copy do the same amount of work So if we do the 'reset' as mentioned in the video: P_Copy does 3 + 2 steps and Q_Copy does 2 + 3 steps. This results in the difference being 0 so no matter where they are in the tree they will always end up at the same place!

[@eddiej204]

The solution sounds like fast slow pointers technique and it is brilliant. Thanks a lot, ser.

[@crackfaang]

Yea it’s super cool. Though a bit hard to come up with if you haven’t seen it before. My mind was blown when I saw the solution for the first time

[@ebenezeracquah478]

Highly appreciated! Bind blowing solution

[@cheekyjay7800]

Brilliant explanation! I got quite confused when I was browsing through the discussion sessions and saw these 5 lines of magic Lol... but your video just made it so clear!

[@crackfaang]

Thanks for the kind words and glad you found value from the video explanation. Make sure to subscribe so you don’t miss future videos!

[@MrDoubleWhy]

Amazing explanation! Thank you!

[@sunwoodad]

You said the time complexity of naive solution is O(2N), but I just think it's O(N). Even the traverse is twice which is by p and also by q, total sum of them won't be greater than N.

[@bhaveshvarma4313]

Thanks man, Now Understand similar question of finding intersection of two linked list.

[@zhengyuzhou2288]

Thank you, that explanation is very clear.

[@rsKayiira]

This is such an excellent solution. I had to watch it twice though because it wasn't clear you would be swapping the pointers so I was wondering but once I figured that out I was like wow. One other thing is maybe calling them q_ptr and p_ptr would have been better and its odd that the examples require us to return values yet we return nodes

[@markvaldez8602]

Awesome! Thank you!

[@JRivero]

So clear. Thank you very much

[@Mo.Abufouda]

This channel is underrated! Great work. Keep the good work! :)

[@crackfaang]

Thank you for the kind words! I'll keep uploading, make sure you're subscribed so you don't miss future uploads :)

[@louie0187]

Basically same "ah-ha" trick as Leetcode 160 -- Intersection of Two Linked Lists

[@crackfaang]

Yup!

[@usrenaem]

Everything is amazing in this video! With your explanation the second solution clicks pretty easily. But what's IQ one should have to be able to solve it at an interview, within 15-20 minutes and without seeing the solution before, it's probably around 160.

[@crackfaang]

You don't need a high IQ lol. You just need to have seen the question before and basically memorized the solution. Just the nature of the game unfortunately

[@sarayarmohammadi3376]

Thank you

[@MinhNguyen-lz1pg]

Well done mate! Appreciate the thoughtful explanation!

[@crackfaang]

Thanks and make sure to subscribe!

[@shraddhabarke1750]

amazing work!! :)

[@dhanashreegodase7933]

thanks

[@preityhansaa9150]

question: if a node is LCA of itself (descendant) meaning it is the parent of itself so do we have to add the same node as parent of itself instead of Null

[@fallencheeto4762]

No way someone figures this out, but it makes so much sense lol

[@bittu007ize]

Love from India

[@crackfaang]

Thank you for your support! Make sure to subscribe so you don’t miss future videos

[@adiesha_]

I am hard time understand why the last solution is linear time. Suppose we have a tree with one left branch of length n-1 and one right branch of length n. Then in order to level the paths you need to run the loop n times, and path length is n. Shouldn't this be O(n^2)?

[@Krankschwester]

The loop wouldn't run N times, but abs(depth of p - depth of q). I do agree that this solution doesn't seem very good. Imagine you have the same example you mentioned but one node is at depth 1e4, the other one at 1e6. You would need to repeat this loop abs(1e4 - 1e6) times, which is awful.

[@preityhansaa9150]

This is good! Thanks for the post. can you post a variation of this for other 2 LCA problems the other ones doesnt have reference to its parent 1644 1676

[@crackfaang]

No problem my friend. If you subscribe I will make these two videos, just for you ;)

[@preityhansaa9150]

@@crackfaang subscribed!

[@tempuser3560]

At 3:39, shouldn't the time complexity be 2*log(n) instead of 2N? We're only looking at the height of the tree in each case

[@adiesha_]

It's not a balanced tree, as far as I understand

[@leetsqlcode1906]

is it |b-a| = |a-b|?

[@n_x1891]

Tortoise hare strikes again