Binary Lifting (Kth Ancestor of a Tree Node)
Вставка
- Опубліковано 29 бер 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.
![ПОЛНАЯ ИСТОРИЯ ЭКЗОРЦИЗМА [Топ Сикрет]](http://i.ytimg.com/vi/qBySr6Bt0B8/mqdefault.jpg)
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 UA-cam..... 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 ❤️
These videos are gold mines, an ultimate treasure. Loved it.
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!!
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.
Yet Again Another Life Saver Video Lecture, I will share this to my friends Thanks a lot!
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 😍😍
Thank you sir, watching your video reminds me a lot when i participated in Math Contest...
thanks for all of this insane useful thing for CP
hope you have more video in the future
Simply amazing, Thanks Errichto.
Thank you errichto keep doing videos about CP_topics which are hard to understand.
Great, please bring more such videos.
Now, It's looking so easy. Thank you.
Nice explanation . Binary lifting doesn't seem tough anymore :)
Extremely well presented, thanks
Thanks for uploading this 😊
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
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
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!
nice explanation. as a beginner, i was able to understand easily
thank you very much for this amazing tutorial
Thanks for the awesome explanation
Just awesome, i hv gone through whole lot of comments, and the coders here are awesome.. great place to Meetup.
Excellent material for CP
What a video man..... Lovely... I really enjoyed and had fun watching it...... #LoveCoding
Beautiful explanation
Thanks for such good content 🙌
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
Very nicely explained 🙂
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
They added the test case you were talking about nodes violating the condition parent[i]
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..
@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
All this time op was like - "This is so simple".
Thanks for the explanation.
Thank you Errichto
Awesome explanation
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...
Awesome explanation.
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
Thanks for the to the point explanation
@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
please do this kind of videos, Thank you!
powers of 2 technique is also used in BIT(Binary Indexed Tree)
thanks its really clear and useful!
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]
best explanation of the world
Finally he remembered that he has a youtube channel. Thanks a ton.
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...
Perfect, Made my day.
Thankyou..Sir,can you please make stream specifically related to mathematical background..
Thanku Errichto🙃
Superb solution. initially hard to understand
🙏🏻🙏🏻got a couple of new thoughts 💛
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
Waiting for game theory related video, sir.🥺
Happy Easter ❤️
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 for this video;
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
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
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!
Thank you so much.
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
@Errichto At 16:30, line 30, you use
if (k & (1
appreciate it! Thanks
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 job
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
Thanks a lot.
Add this video to the Edu playlist please
done
How depth[v]=depth[parent[v]]+1????
This holds if depth[parent[v]] is already computed which is not always true.
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)
Thanks !!
nice video
What hardware/software do u use to teach and write?
waiting for sparse table lecture
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
Thanks pls do graphs dfs and bfs.
Can you please explain to me why this code only solving cases where parent[i]
Errichto your code isn't working for this problem, you have to use the dfs method to do preprocessing.
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 :-)
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.
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
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
What's the tool you use to draw man?
Very Nice Explanation 😍.
I think you calculated depth in wrong manner
consider this case:
["TreeAncestor","getKthAncestor"]
[[6,[-1,2,3,4,5,0]],[1,4]]
depth array according to code will be [0,1,1,1,1,1] but it should be [0,5,4,3,2,1]
and for node = 1, 4th ancestor should be 5 but it will give -1 as depth is wrong.
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.
Is the github solution fine? it gives some error on one of the leetcode estcases
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.
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
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.
Though the provided solution does look correct, it doesn't pass 5 out of 15 test cases on leetcode :(