Lowest Common Ancestor (LCA) Problem | Eulerian path method

[@codecode855]

we can use segmented tree instead of sparse table for RMQ. my solution got accepted !

[@vishaltk3013]

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.

[@olehholovko1341]

Thanks, your videos are great! I will definitely explore more soon.

[@alkhiljohn3813]

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

[@Blure]

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?

[@tashirojima]

Such an elegant algorithm! Thank you

[@ialpha6431]

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.

[@WilliamFiset-videos]

Thank you Saurav 🙏. You're correct, you can swap out the sparse table for any other data structure that can do a RMQ

[@madhukiranattivilli2321]

But LCA can be computed in O(1) time only w/ Sparse Table. Segment Tree does in O(log2(n))

[@matata.rishikesh]

The music at the start is also very good

[@HienNguyenTechIO]

Please make more videos. You channel is very well explained.

[@mohammadyahya78]

Thank you. Still not sure why you visited node twice 14:50 please?

[@akshatsaxena5156]

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.

[@Ghost0fDeath1]

Ty I did my project for uni with this

[@nguyentuan6108]

bro deserves a 10

[@Zoro40612]

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

[@WilliamFiset-videos]

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.

[@Zoro40612]

WilliamFiset Cool. Thanks for the videos! 🤟🏻

[@protyaybanerjee5051]

@@WilliamFiset-videos So, essentially we have O(1) amortized lookup cost.

[@Aashishkumar-dg4op]

Thanks a lot for sharing your knowledge.could you make videos on centroid decomposition.

[@swethapattabhi2916]

Amazing explanation.Thanks a ton!

[@bhimeshchauhan3081]

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.

[@mnhr7494]

This was awesome!!!

[@hwgh]

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!

[@WilliamFiset-videos]

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?

[@hwgh]

​@@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!

[@935k3]

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...

[@935k3]

Doh, just realized I glossed over the index table within the sparse table! 🤦

[@BerArchegas]

Great channel

[@prasannathapa1024]

This is golddddd

[@nhan99dn]

goat

[@PrashantNigam]

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

[@manushakya7384]

Thank You

[@rushilpatel7671]

awesome !!

[@adhishmalviya2408]

138 Likes and 0 Dislikes !!

[@Rakibul-Hasan-Mahin]

anyone solved this in python?? if yes can you kindly share?

[@dongliang8837]

why is the volume so low. I have my computer on max volume and i can barely hear