hey everyone welcome back to my channel the new video in this video we're covering another nice uh question of a binary search tree which is uh you're given a binary search tree and uh let me just bring up my iPad here okay so you are given a binary search tree let's say you have five 7 6 this would be let's say 8 3 4 2 1 let's say this is the binary search tree that is given to you what the problem is that uh two nodes in the binary search tree are swapped it can be any two nodes it can be any two nod so let's say this one this one are swapped 7 and two okay so these two nodes are swapped now it can be any two nodes we know that uh how are we going to solve this one of the ways you can solve this is you can imagine that let's say if this is a binary search tree and we do in ordered reversal then we know that it will be a sorted array so if it is a sorted array so in order reversal before the swapping the sorted array would look something like this 1 2 3 4 5 6 7 8 this is what it would look like but what has now happened is 2 and seven have been swapped 2 and seven have been swapped so this question now becomes that okay in a sorted array Which two elements are swapped this can be very simple you can just check the previous one so there will be two violations one violation is over here one violation is over here s is greater than its previous element two is less than its previous element okay two violations so that is what we have to find these two violations we have to find in our binary search tree so what we're do is we're going to take the first violation is equal to initially null second violation in equal equal to null whenever we find the first violation so the first violation will arrive when we say that the current node that you are at so it's in order reversal is what left current then right so if I am talking about the current node it means left is already been visited so I'm going to be like let's say I go here then I come here then I come here here I say if left node is less than the previous node it means that first has been found which is equal to previous node because this is the previous one previous node and then we know that we will find the first one first because it comes first so we'll say if first is not equal to null means first has been found if first not equal to null first is equal to previous node then we will keep on uh going we will now go over here this looks fine we will come over here then we will come over here this looks fine we'll come over here we'll do the same condition if this not left it is the current node current current node that you are at now we are at current node if current node is less than the previous node yes it is in this case we will say that the second node that is wrong is equal to what previous no previous is six the current which is the current node current and that's it after that we will just swap these two because these are just pointers to these nodes let references to these nodes that's it pretty simple I told you when I was teaching uh like link list when such questions are given you don't have to think you just have to do what the question is saying and this is what the question is saying okay you do understand how I'm making these previous right so first of all I will have whenever I choose this this will be previous then I evaluate this this will be previous then I evaluate this I will do this then this will become previous whenever you keep evaluating make it previous okay okay if a current node is evaluated that is previous then I will go here this will remain previous and this will become previous then I will go here so on and so forth okay very simple pause this video think about it and uh by the what is the time complexity going to be for this solution we are visiting every node only once and uh there's the recursive space also so we are taking o of n time right that's what we're doing and uh for the tree we are only doing in AIT reversal so it's the height of the height of the tree okay so here you can see on the screen uh can by the way find the link in the description uh below as well for this code so the question was two node swap so we're going to create two node swap. Java first of all I'm going to say class class node int value node left node right public node in val this dot val is equal to Val The Constructor is done all good looking nice now public Class 2 node swap here I'm going to create my node first okay initially that is null node second and I'm going to create a node previous that is also initially equal to null I'm going to say public void I'm going to call this one um helper okay and I'm going to pass node let's say for the naming convention root over here I'm going to call in order traversal on the root node while when I have done in order reversal these two will be populated so I will just swap so I will say first or I will just say if I want to swap it um yeah let's say ideally I just swap the let's say just the values are interchanged okay to make things simpler but you can swap if the entire nodes are interchanged as well so I can say first dot val first. Val is equal to second do Val second do Val is equal to Temp so okay initially now we we assumed that only the values are swapped so you can uh you know swap the entire nodes as well but you are pro experts in that so you can do it yourself now private void in ordered reversal node node now I will just do in ordered reversal if node is equal to equal to null return that's it just return in order reversal node do left node do right and in the middle we will do the work that is what inord reversal is so what is the work that we're doing check if the previous node is violating the binary search Tre property so if the previous node do value is actually greater than the current node do value also so that we don't get null pointer exception if previous node is not equal to null and then I will check if first node is equal to equal to null in that case I will say that I have found the first violation this thing first violation so I will say first is equal to previous otherwise I will say second is equal to current which is the node okay then I will say previous is equal to current node that's it very simple stuff problem solved okay very cool okay that's pretty much about it very simple solution and we did a trial run as well you can try running it if you want uh it's very easy just to create two trees and uh if you have any questions let me know in the comment section below and uh we'll be continuing the boot camp and introducing newer Concepts um you know in the next new year and uh I want to wish you all a Happy New Year as well and uh yeah see you next year bye