Binary Lifting (Kth Ancestor of a Tree Node)
Vložit
- čas přidán 29. 03. 2021
- Tutorial on binary lifting (also called jump pointers). We find k-th ancestor of a node in O(log(N)). Problem link leetcode.com/problems/kth-anc...
Final code github.com/Errichto/youtube/b...
Coding live streams - / errichto
FAQ - github.com/Errichto/youtube/w...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
The perfect video to find before going to bed :)
Finally I meet someone who feels the same... Even before going to bed, I can understand this guy's explanations in a short time, what a legend!
Aah, that connection when you feel the exact same way as a complete stranger on CZcams..... The Internet did break many walls
Thank god...I'm trying to understand this for a week now...
I hope it doesn't take another week with my video :|
@@Errichto it will surely not....😊
@@Errichto if I want to find minimum number of numbers(power of 2) that sum upto some k. Does this approach hold?
@@deepeiton6112 Yes, this idea is used in LCA. If you want, you can ask something particular and I will answer you.
@@deepeiton6112 As far as I understood, you asked, If it's true, that any number can be represented as the number of sums of two. The answer is Yes, you can find this powers of two greedy. Go from bigger powers of two to lower.
Example: 49 = 32 + 16 + 1, or 90 = 64 + 16 + 8 + 2.
Good way to do it in C++:
vectorpowers;
int num; cin >> num;
for (int i = 30; i >= 0; i--){
if(num - (1 = 0){
num -= (1
I always tried with O(n) way....thanks for this O(logN) way.....nice explanation....👍👍
I'm a beginner at CP but still was able to understand much of this, Thank you for such an amazing explanation Erichto ❤️
Yet Again Another Life Saver Video Lecture, I will share this to my friends Thanks a lot!
Thank you Errichto! I'm a new subscriber to the channel and you've really helped me a lot! Your explanations are far more better than my mentors in school. TYSM!
Always love your explanations, the best stuff out there.
Very thanks for the clear explanation. I understood it again very well. Thanks a lot, Errichto!
Thanks Errichto, just cz you have made the video, I gt to know a new concept I never heard about! Keep making such videos!! Helps a lot!!
this guy learned english, and computer science and how to explain things clearly and put it all on youtube for free so us dumb people can learn, what a legend
Simply amazing, Thanks Errichto.
Incredibly chilly vibe, good explanation... overall great video, thanks!
I like to add just another node (N+1) above the root and parent of (N+1) is itself. now at every query if the ancestor (N+1) return -1
Good idea! No depth needed then.
great idea 😍😍
thanks for all of this insane useful thing for CP
hope you have more video in the future
Thank you errichto keep doing videos about CP_topics which are hard to understand.
Thank you sir, watching your video reminds me a lot when i participated in Math Contest...
Thanks for uploading this 😊
Extremely well presented, thanks
Great, please bring more such videos.
Thanks for the awesome explanation
Now, It's looking so easy. Thank you.
Nice explanation . Binary lifting doesn't seem tough anymore :)
thank you very much for this amazing tutorial
Thanks for such good content 🙌
Beautiful explanation
Thank you Errichto
yo this vid came in clutch been trying to understnad this problem.
who is here after edu 110 div 2 , thanks a lot i solved E after watching this
Excellent material for CP
All this time op was like - "This is so simple".
Thanks for the explanation.
Thanks, just realized this was the hardest leetcode question in Tree segment, helped a lot...... One small addition in the last part is that we don't need to calculate depth if we just check that node is -1 in each iteration
code -
for i in range(self.log):
if k & (1
you are right, I also implemented it this way, but he said that he didn't want to add extra steps in the pre-calc to make this work and preferred the depth way!
Perfect, Made my day.
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thanks for the to the point explanation
Awesome explanation
They added the test case you were talking about nodes violating the condition parent[i]
thanks its really clear and useful!
Very nicely explained 🙂
nice explanation. as a beginner, i was able to understand easily
Thanku Errichto🙃
@Errichto - At 11:21 : You say "And there's this condition about parents which is also quite convenient". I don't think that's the condition you mean. The condition at 11:21 is parent[ i ] < n, which is NOT the same as : parent[ i ] < i
Same doubt
please do this kind of videos, Thank you!
Awesome explanation.
Just awesome, i hv gone through whole lot of comments, and the coders here are awesome.. great place to Meetup.
The same code is giving WA in test case [4,[-1,2,3,0]], [2,3], [2,2] , [2,1]
U considered the nodes to be in increasing order from top to bottom, dats why it failed when the nodes are in decreasing order..
What a video man..... Lovely... I really enjoyed and had fun watching it...... #LoveCoding
We would be grateful if you would ever make a proper series, or course for competitive programming..
From medium to very advanced methods concepts to solve hard competitive programming problems...
🙏🏻🙏🏻got a couple of new thoughts 💛
I think leetcode has changed the question a bit now, now it is not necessaary that parent.value < node.value
what I did to solve this is find the order in which nodes appear so like using bfs and then applied the same
// code
class TreeAncestor {
public:
vector bfs(vector& arr,int i){
vector res, visited(arr.size(),0);
queue q;
q.push(i);
while(q.empty() == false){
int len = q.size();
while(len--){
int node = q.front();
q.pop();
visited[node] = 1;
//add to res
res.push_back(node);
for(int j: arr[node]){
if(visited[j]) continue;
q.push(j);
}
}
}
return res;
}
int LOG = 20;
vector dp;
TreeAncestor(int n, vector& parent) {
//make tree here
vector arr(n);
for(int i=1;i
Cool lecture man.
I used to think there was some sort of relation between binary search and binary lifting. Well there indeed is a relation, but not exactly. I still kinda hate how some chinese contestants use the word "binary search" and "binary lifting" interchangeably, although........I sort of understand why, especially if you into a habit of writing binary search using for loops instead of while .
There is a bigger similarity if you implement binary search by using powers of two. Say that you are searching in range [L, R].
for(int i = 19; i >= 0; i--) { int mid = L + (1
@@Errichto I love you
powers of 2 technique is also used in BIT(Binary Indexed Tree)
Happy Easter ❤️
Thankyou..Sir,can you please make stream specifically related to mathematical background..
Finally he remembered that he has a youtube channel. Thanks a ton.
Waiting for game theory related video, sir.🥺
Thank you..
could you please make a video on how to code branch and bound with the example on travelling salesman problem, knapsack problem or any other example.
I want to know how to find the next children of the parent and how to get the final solution
best explanation of the world
thank you for this video;
Video request: string algorithms (KMP, Manacher). They don't occur often on CF but do on ICPC and I would like a nice resource (there aren't any nice video resources on these topics).
Thank you so much.
For case where we need to return "-1" : How about for every query we can calculate both Kth and (K-1)th ancestor. If they are equal we return -1 else we return Kth ancestor
I think you can't do that if k == 1. if k == 1, then we're gonna check the ancestor with distance 0 and 1. errichto's implementation itself i think it is unsuited to find the ancestor with distance 0. but if you make a if else statement, i think you can...
Superb solution. initially hard to understand
@Errichto 15:38 you dont need to change any condition for log calculation, All you have to do is to change the iteration in loop from j=0;j
appreciate it! Thanks
Thanks for the explanation really helped a lot ,
Now As the condition is parent[i] < n , loops order will get changed and we can avoid depth track too
int[][] up;
int log = 17;
public TreeAncestor(int n, int[] parent) {
up = new int[n][log];
//assuming 0 is the root node
parent[0] = -1;
//setting up first ancestor
for( int i = 0 ; i < n ; i++)
up[i][0] = parent[i];
//setting up other ancestors
for( int j = 1 ; j < log ; j++)
{
for( int v = 0 ; v < n ; v++)
{
if(up[v][j-1] == -1)
up[v][j] = -1;
else
up[v][j] = up[ up[v][j-1] ][j-1];
}
}
}
public int getKthAncestor(int node, int k) {
for(int i = 0 ; i < log ; i++)
{
if(((1
Can you please explain to me why this code only solving cases where parent[i]
Thanks a lot.
@Errichto At 16:30, line 30, you use
if (k & (1
Hi Errichto, thank you very much for your tutorials, please consider possibility to make background of your videos little less black, for example blue dark or silver dark to make them more neural, I think that in that case watching your videos will be less stressful for the eyes, thanks
Dark gray seems neutral enough, I think.
@@Errichto ohhh, I watched several yours videos in parallel, black background is present on your first tutorials. Good luck in Code Jam competition
nice job
More leetcode problems pleasee. Just go crazy and solve all leetcode problems and put them into a playlist
that's a lot of videos :|
@@Errichto That's true. Normal mortals can't do it. But someone like you can just rush through most problems, you can use your strengths to the fullest and bring value to the world that others can't. Just read a problem, state your thoughts and approach, code, next problem.
@@MrDivad006 nah, rather have him do lectures like these and you can try solving all the problems with the concepts he teaches
Thanks !!
Thanks for the wonderful lecture.
But I am a bit confused about the way depth[v] and up array have been computed in the leetcode problem, it is never mentioned that parent[v] < v. If this condition is not true then result should be incorrect. Right? Or I am missing something.
Yeah, you are correct
How depth[v]=depth[parent[v]]+1????
This holds if depth[parent[v]] is already computed which is not always true.
Superb video Errichto, would you be interested in making some String algorithms videos? Suffix array in NlogN, Ukkonen, Manacher, Hashing(This is going to be super informative, if you include the anti-hashing test breaks that were mentioned on codeforces a few years ago when you use overflow), Suffix Trie and use cases, Compressed Trie?
This will add so much more value to your already amazing channel!:) Much thanks!
When we exchange the for loops, (where the LOG for loop is before) will work in both cases (independent of the value/order of nodes) while calculating the up vector?
yep that'll work in both cases
I understand that if "parent[i] < i", then you can safely compute the parent array for each V in increasing order.
However on leetcode it states that "parent[i] < n", which is a different thing, no?
Thanks for the video!
Oh, good catch. I've misread the condition as "parent[i] < i". Then my solution shouldn't work with the current order of for-loops and the test data is apparently weak.
@@Errichto Hey, thanks I have contributed a test case to Leetcode so that this fails. Sorry but now your code also fails.
@@jahnvikumari318 Cheers for that!
@@jahnvikumari318 🥲
you are right. I used a visited array and called another function to compute for a node if it is not visited yet. i was confused on how his code passed the test cases. now i understand that test cases were weak in the past
nice video
Thanks pls do graphs dfs and bfs.
Sir, May I have any advice on How and when to turn my kids to Math from your perspective ? They are 2yo, and I’m preparing now)
Add this video to the Edu playlist please
done
waiting for sparse table lecture
Hey Errichto , What can we do
..if we have two types of quries in which one query type is we can add or delete leaf node in tree and other type return Kth ancestor !?
Easy: just compute all log(N) needed ancestors when adding a new leaf. No need to do anything when removing a leaf.
@@Errichto thanks a lot :-)
Can you please explain to me why this code only solving cases where parent[i]
I´m trying to solve a similar problem but I need to calculate the sum of a given node and a number of parents ex: node 2 and 5 parents and l have to return the sum of the values of that nodes. Any ideas of how can calculate the sum if i have the table with the k ancestros
Hi, you mentioned since input n can be upto 50k, quadratic runtime won't work. What is the limit of input till which quadratic would work and why? Thanks!
if you're talking about the brute force then till n
What hardware/software do u use to teach and write?
Is the github solution fine? it gives some error on one of the leetcode estcases
2:38 I think segment tree is divide and conquer approach ??
Yeah, in some way it is. What I meant is that segment trees and fenwick trees are often implemented for perfect powers of two.
Can we use fenwick tree trick for jumping to parents for finding kth ancestor?
currently, if k = 21, we are jumping like 1 then 4 then 16. How about we jump in reverse like 16 then 4 then 1?
we can use following to move to 16 from 21:
int nextJump = k & -k;
then
k -= nextJump; // this makes k = 5 again
and we repeat same.
What you described is another way to get the binary representation of K. It's just commonly used in Fenwick trees.
what is software you used to present
why could you use node that has not been calculated? I mean this part: for(int v=0; v
What's the tool you use to draw man?
Errichto your code isn't working for this problem, you have to use the dfs method to do preprocessing.
The condition of the leetcode problem has changed. Now you will need to swap the loops. XD
Bro I have a doubt , while debuging a program in vscode which uses array of string. I want to see all the elements while debuging, but it does not show like that. I need yr help bro. I stucked in that for 3 days..please if anyone knows help me.
google kr le bro
when i did the question on leetcode par[i]
Instead of depth can we check if node == up[node[j]] return -1
Are you trying to check if node is the root? I don't see how that helps.
I meant instead of depth. We could go up the tree and if we get the condition we return -1.
Code is not working for some test cases now.
Though the provided solution does look correct, it doesn't pass 5 out of 15 test cases on leetcode :(
Why are you using log(n) instead of log(height of tree) in your implementation ? The n (number of nodes) must be larger than height.
Log2(n)+1 will provide the height of tree only, you can even use this condition to get you log value and it will work.
@@sudhanshukumarroy7018 Did I understand correctly that n is a height of the tree in a worst case scenario ?
That's why I suppose for worst case tree we will get higher order ancestors rather than getting -1 too quickly in a binary tree like tree.
It is supposed like log value is the value whose 2^LogValue will provide highest possible ancestor that can exist.