LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]
ฝัง
- เผยแพร่เมื่อ 12 ก.ย. 2024
- 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.
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 :)
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!
The solution sounds like fast slow pointers technique and it is brilliant. Thanks a lot, ser.
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
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!
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!
this channel is real af,
This channel is underrated!
Great work. Keep the good work! :)
Thank you for the kind words! I'll keep uploading, make sure you're subscribed so you don't miss future uploads :)
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
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.
So clear. Thank you very much
Thanks, bro, really good explanation, love it!
Great explanation. The two pointer solution is exactly similar to Intersection of two linked lists problem. In an interview, would we be expected to come up with such a solution or will the set solution suffice?
Awesome! Thank you!
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.
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
Thanks man, Now Understand similar question of finding intersection of two linked list.
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)?
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.
Thank you, that explanation is very clear.
Basically same "ah-ha" trick as Leetcode 160 -- Intersection of Two Linked Lists
Yup!
Thank you
Amazing explanation! Thank you!
Highly appreciated! Bind blowing solution
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
No problem my friend. If you subscribe I will make these two videos, just for you ;)
@@crackfaang subscribed!
Well done mate! Appreciate the thoughtful explanation!
Thanks and make sure to subscribe!
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
amazing work!! :)
Thanks. bro next time use different colors for the drawing.
No way someone figures this out, but it makes so much sense lol
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
It's not a balanced tree, as far as I understand
is it |b-a| = |a-b|?
thanks
Love from India
Thank you for your support! Make sure to subscribe so you don’t miss future videos
This is how i got 400 k plus meta offer
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
seen = set()
while p:
seen.add(p)
p = p.parent
while q:
if q in seen:
return q
q = q.parent
return None
Tortoise hare strikes again
You need to work on your rationale. Yes you reach the answer but it's not clear why.