Dynamic Programming on Trees: LCA using Binary Search

[@Newgen123Blogspotawaytosuccess]

Sir, This was the best explanation I've ever seen. Please continue doing this great work. Got to know about your channel yesterday and till now I have watched every video of dp in trees playlist. Waiting for more such content.

[@AlgosWithKartik]

I am happy to know that you are finding it helpful! It would be great if you could share it with your friends too :)

[@Newgen123Blogspotawaytosuccess]

Definitely...

[@KaranYadav-gr5xj]

"The code is quite simple to understand and gives a very good TLE" 😂😂

[@ankitbhardwaj9566]

bhaiya i am also from dtu ,just for god sake ye cses ki problemset me jitne bhi ache questions apko ache lage har topic me se unke upar video zaroor banana

[@pranshunayak1792]

Best video till date!!

[@adarshkumar6876]

Please share the code

[@princhipawansaikia]

Great Explaination !!

[@p.adityakumar1762]

Sir, i implemented a very similar solution using binary lifting and binary search. I did almost the same thing that you did. I just used a single checkancestor function to see if the uplift by y nodes would give a common ancestor or not, and it got accepted. I wanted to ask that if using only one checkancestor function ( which is the very similar and has equal time complexity to getnode function) instead of two getnode function , should it affect the time complexity because it takes O(logn) time only.

[@AlgosWithKartik]

I think the only difference here is the constant factor. I feel my code would have also got AC if the time limit was 1.5 secs. What is the time needed for checkancestor() function? If that is O(1) then your algorithm is O(logN) instead of O(log^2N) which I achieve using binary search. Can you share your code, I would like to have a look :)

[@p.adityakumar1762]

@@AlgosWithKartik the checkancestor() function has O(logn) complexity. Here's the code ideone.com/xWKIAU

[@AlgosWithKartik]

@@p.adityakumar1762 I guess then your code would have just passed. 0.8 or 0.9 sec in execution time. Nicely implemented.

[@khanakpatwari2587]

can you share your code in replies section? It's not visible now in case you had shared already

[@aadarshktofficial]

Please can you also give the link of code on github.

[@Newgen123Blogspotawaytosuccess]

One doubt only... in order to find the level of each node. Time complexity is O(n) ... So, Shouldn't overall time complexity be O(n)???

[@AlgosWithKartik]

Actually the idea here is that, what is the time complexity per query. We can preprocess the levels for each node in O(N) and thereafter each query will cost us log^2N or logN time. So yes overall time complexity is O(N + QlogN) where Q is number of queries we need to answer and is more efficient than O(NQ). Also include time taken to build "up" array in preprocess step.

[@Newgen123Blogspotawaytosuccess]

Thnx sir.. now i got it