Lowest Common Ancestor (LCA) Problem | Eulerian path method
HTML-код
- Опубликовано: 8 фев 2025
- Lowest Common Ancestor problem
Lowest Common Ancestor source code video:
• Lowest Common Ancestor...
Sparse Table Video:
• Sparse Table Data Stru...
Source code repository:
github.com/wil...
Video slides:
github.com/wil...
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
Thanks, your videos are great! I will definitely explore more soon.
This is damn good. I felt guilty for consuming this content for free and purchased the Udemy course. this may be one of the reasons why we see lesser views for videos as this course progresses further.
we can use segmented tree instead of sparse table for RMQ. my solution got accepted !
Thanks!
So glad to know this guy has a soul and cares about investing time into teaching random people on the internet. I wish I could pay him back
Practice problems for this concept:
* leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree
* leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii (LC Premium)
* leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii (LC Premium)
* leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv (LC Premium)
* leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree
* leetcode.com/problems/kth-ancestor-of-a-tree-node
Hello William! Thanks a lot for sharing your knowledge. Could you consider making a video about space-partitioning data structures, such as K-D tree, Quadtree and R-tree?
Such an elegant algorithm! Thank you
This is GOOOOOOOOD ! Very well explained. Now I know one more method to calculate LCA. Since, I am not currently familiar with Sparse table I guess any DS good in doing range queries (Segment Tree, BIT etc) can do the trick.
Thank you Saurav 🙏. You're correct, you can swap out the sparse table for any other data structure that can do a RMQ
But LCA can be computed in O(1) time only w/ Sparse Table. Segment Tree does in O(log2(n))
Please make more videos. You channel is very well explained.
Ty I did my project for uni with this
The music at the start is also very good
Amazing explanation.Thanks a ton!
This was awesome!!!
Your content and explaination is really good. But please do something to improve the sound quality, its too low and not audible sometimes.I am facing this issue in all your videos.
bro deserves a 10
Great channel
Thank you. Still not sure why you visited node twice 14:50 please?
Thanks a lot for sharing your knowledge.could you make videos on centroid decomposition.
Do one on binary lifting
This is golddddd
Thank You
Hello William. Why use a sparse table to lookup the minimum of a range in depth array? It takes O(nlogn) to construct it. We can get the minimum value of a range from depth array with a simple for loop in O(n).
What about if you want to do multiple LCA queries? I would prefer to build the sparse table once and have each lookup be O(1) than have to pay O(n) for each query. The payoff point is reached once you've done log(n) queries which is very small.
WilliamFiset Cool. Thanks for the videos! 🤟🏻
@@WilliamFiset-videos So, essentially we have O(1) amortized lookup cost.
awesome !!
I'm not sure I get why we need an Eulerian tour here. If we used a N sized array instead of 2N-1, and visited the three in-order always saving the pointer to the node and the depth. We would end up with an in-order array of tuples (nodes,weights) correct? In the video example we would have [ptr:3 dpt:2,
ptr:1 dpt:1, ptr:0 dpt:0, ptr:6 dpt:3, ptr:4 dpt:2, ptr:2 dpt:1, ptr:5 dpt:2, ].
Won't the property of the common ancestor being the one with the lowest depth that is between the two nodes still hold? It seems to be the case to me. What am I missing? Is it related to supporting non N-ary trees?
Thanks for the great content!
I don't think storing only N information is sufficent for n-ary trees? Suppose we had a very flat tree like:
0
/ / / / | \ \ \ \
1 2 3 4 5 6 7 8 9
Can you explain how you would define the in-order traversal to query the lowest common ancestor of say node 2 and node 4?
The Eulerian tour ensures that 0 appears between 2 and 4 in the tour, but I'm not sure this is true of the inorder traversal?
@@WilliamFiset-videos I see. It really does make it work for N-ary trees. I think what happens is that the first visit (the one that happens before the "for") isn't really necessary unless the current node has no children. If we don't do it, all the nodes that have children will still work. The visit in the last iteration of the for doesn't seem to be necessary as well.
So if we changed dfs for this:
if node==null
return
if node.children.isEmpty
visit(node,node_depth)
for( child in node.children )
dfs( child, node_depth+1)
if (not child.isLastChild) or child.isOnlyChild
visit(node,node_depth)
This code would still insert the parent in between every child and it would work. ( Unless my reasoning is wrong somewhere ).
Then for a binary tree this would behave exactly like a in-order search and this is the reason why in-order search works for a binary tree.
And then for N-ary trees every iteration (but the last) will be visiting the current node again thus inserting the parent in between the children every time. I think this is it. Right?
Thanks again. Your channel and your explanations are great!
goat
Can we not do Level order traversal and then use the formula for the respective nodes to find the LCA until we reach a common number in the list or we reach the root which would be the first item in the list. The complexity should remain the same.
So after watching the sparse table videos following this one, I'm trying to tackle an LCA problem on leetcode. The sparse table I've built simply returns the depth of the LCA since the table is based on the depth array. Going by the code in this video, it seems that the sparse table returns an index to plug into the nodes array. Not sure how to move forward from here...
Doh, just realized I glossed over the index table within the sparse table! 🤦
138 Likes and 0 Dislikes !!
anyone solved this in python??
if yes can you kindly share?
why is the volume so low. I have my computer on max volume and i can barely hear