Insertion of Element into BST - Binary Search Tree | Mr.Srinivas

hi everyone welcome to nourish technologies this is in verse so in the last session so we discussed the introduction part of a binary search tree in a data structures and algorithms so now in this session we'll see so what are the operations so we can perform on a binary search tree right so we can insert the elements into binary search tree right so we can delete the elements and we can traverse the elements so first we will see how to insert an element into binary search tree okay here insertion of element into binary search tree into binary search tree so first we need to create the node so how to create the node structure representation already we discussed very clearly struct node is at most having free fields right so one is a data field to store the information and next one so left child a pointer to left child and next one pointer to right child so this is a structure so first initially we need to declare a global variable just like in a single linkedlist and double linkedlist concept here also we need to declare one global variable struct node star that is a root element so what is the initial value is a null and of course a global variable default value pointer type default value is always null but if you want to show very clearly then you can write this null so then first root variable will be created and then we need to store the information so first I will explain the process of storing information into binary search tree okay see see for example so first root is not pointing to anything is nothing but root equals to null is not pointing to any node suppose you have to create a node node so directly we are writing in the form of a circle just consider and I am storing some information for example 50 and XR where you have to connect that first we need to check whether the node means what whether the root is pointing to any node or not so nothing but a tree contains any nodes are not right so this is the first node we created right so that directly route should pointing to this node is the first node it is a root node next suppose if you want to connect to some other nodes first and right some of the things for example 60 I want to connect is connected to right side next 170 I want to connect is connected to right side 50 I want to connect when compared with the mean 55 compare with the 50 55 is a greater value and come to here when compared with the 60 it is a lesser lesser value so it will be connected here left side also some elements I am storing for example 30 and X 120 so like that we are storing some elements now I want to create a node so first we need to create for example node value this consider 57 is a node value so I am creating in node 57 is a node node is ready but where we have to connect it we need to start searching from the first node if root is pointing to null means what what you have created is a first node but suppose if list already sorry if a tree is already having some nodes then you have to connect to where we have to connect it we need to travel from root node to that particular parent node okay first we need to compare with this one current node right that parent node next we are moving next we are moving like this okay and this is we should consider it as a parent node parent node so now so we found the and node next the node what you want to connect newly created node where we have to connect a pair into left side or pair into right side how to connect them so that is important here here suppose if parent data is less than or a current data is greater than the parent data then we are connecting to right side if pair means what if current node data is less than the parent data then we have to connect it to left side simple thing okay so this is simply a connection how to insert a node right so now we will write the logic for this and you will get more clarity on this okay see the code we are writing about the function name we are writing void insert function insert function so what we want to insert that we are collecting into D already root variable is there so root variable is there root is pointing to null root is not means what is pointing to null next here in an insert we are creating one node so what is that one a temporary variable we are creating struct node star E is a temporary node we are creating so T gets memory allocation somewhere he gets memory allocation now we need to create the node first so we know that how to create so using ml log and here it is we need to pass the sizeof struct node the sizeof struct node we are passing and that we are collecting into E and here it is a typecasting I am NOT writing completely struct node star you have to write it we know so many times we have discussed so this is a memory allocation the node will be created here and node will be created with three fields at some location thousand the thousand will be collected into P so temporarily it is pointing to this node next data we need to store here it is a D value into E is pointing to this node into e to data we are storing the D value and next left-side child right child right side shell is a null so t2 left equals to null e to right equals to null equals to null so now node is ready suppose value is just consider 50 50 left side is a null right side is a null he is a temporarily is pointing to this node right is once you connected permanently then the local variable temporary variable will be deleted automatically next where we have to connect all right so first we need to consider the variable as a parent variable also one more point is a parent P is nothing but a parent okay into the P we are taking root value root value first actually this is for remaining connections what I am writing here and next observe a suppose here if root equals to null so what it is representing means right the tree is not having any nodes at what the node you have created that is the first node so by the time root should point into the newly created node only so very simple the thousand you should store in a root so here it is at a value we are storing into root so connection is over finished here a value thousand will be stored here this is the case this is first node yes we are creating the node creating and next we are storing the information storing the information and next one we are checking root equals to null or not and if it is root equals to null means which is not pointing to any node in the tree so what the node you have created is a first node so that newly created node address we are assigning to root is clear first node connection is very easy sir what about our remaining nodes creation what about a remaining nodes creation insertion right that will see else block okay so followed by whatever the logic that I want to write clearly look at this see to understand easily right so first I will draw one tree so with a few nodes okay see for example root is holding just consider first node address this is a first node first node is a 50 next this is one node this is one node 60 this is one node 70 this is one node 65 just consider and here also we are writing some nodes like a 30 and next 20 some nodes 25 base addresses also I am writing thousand so that it is pointing to this node 2000 3000 4000 5000 6000 7000 addresses random addresses we know that for this left-side connection is there mm is pointing right side connection is there 3000 is pointing for this right side connection is there 5,000 is pointing but left side no connection null value for this left side connection is there here it is a 6000 is connecting no right side connection here it is no right no left and this one left side connection is there 4000 is connecting to this one no right side connection for this one right side connection is there 7000 and no left side connection null null null this is a tree with a few nodes so we followed all the binary search tree rules we know all the rules how to insert now I am inserting the new node okay first I have created the node we know how to create the node for example node value is a 67 important this is the node I have created the node value is a 67 and address is a 8,000 consider initially null and null who is pointing II is pointing Emperor II variable is holding the address 8000 just now we have discussed how to create the node how to store the data how to make it left chill and right places null fields and how to store the information into a node is ready next how to travel from first location to last location that is very very important look at this if block logic already we have written now we are writing else block logic very clearly already variable parent variable we are maintaining in the parent variable value root value is there so what is that root value thousand next inside the else block we are creating one more variable struct node star this is a current node we are declaring in the current also we are storing that root value so current also we are storing the truth-value root value is also thousand yes now how to travel from first location to last location to connect this node here how simple with the help of one while loop while current see you are are see here current value is a thousand thousand is a true value so while loop executes control come inside now we should send the control to left side or right side that you should understand node data is what is a 67 67 we need to compare with the 50 we need to compare with a 50 50 is nothing but a parent or we can call it as a current also no problem okay simply here it is a e 2 node data here if if e 2 data e 2 data is greater than current 2 data is greater than current 2 data so what is that current data thousand two data is a 50 and it is a greater than so we should move to right side or left side we should move to right side because it is a greater than so simply e to current to current to so right will be stored in to current so current to right means thousand to right is what is a 3000 3000 will be stored into current else left value so what is that left value what is that left value means here it is if it is a lesser value than 2000 will be stored simply current to left value will be into current this is but every time whenever we are storing that current value is assigned to parent because we are finding that parent value is P is a parent you can write our P we can write so current value is a thousand next once again it will repeat while current what is the current value three thousand observed while three thousand condition true three thousand will be stored into parent parent is now 3000 3000 next a two data is greater than current two data what is T two data is a 67 is greater than current or data current two data is what current is 3000 3000 two data is what is sixty sixty seven is greater than sixteen are again condition true so current to write value will be stored into current what is the current to write the 3000 to write is what is a 5000 so 5000 will be stored into current one more step we are moving again while loop while 5000 condition true that current value will be stored in to parent here current value here it is simply so current to data current value will be stored in to parent here parent value is a 5,000 next again if t2 data is greater than current to data now t2 data is a 67 but current to data is a 17 so condition falls 67 is greater than 70 condition false it will fail else block execute now current to left will be stored into current current to left is a 6000 this one now left side moving because LS value that is simply 6000 will be stored here 6000 and next one here it is again it will repeat current value will be stored into parent that is nothing but 6000 will be stored here 6000 and next one again a two data is greater than current two data here it is a 67 is greater than 65 yes condition true then current to write value will be stored into current a current to write value 6000 to write value is what null value that null value will be stored finally into current null value will be stored next time whenever we are repeating while current the current value is an ulnar so condition failed then while loop will be terminated finally we found the parent value where we have to connect the child C so parent is pointing to parent either parent or P you can write okay I think I declared P here it is parent is pointing to the node where we have to create the new node but directly you can create once again we need to check if t2 data is greater than parent parent to data then connect the right side if it is a lesser value suppose 63 be connected to left side once again after while loop execution if t2 data is greater than pair into data pair into data please connect that e to Aaron - right here it is so clearly am writing a value we are collecting - parent - right so what is the T value is a 8000 67 e to data 67 is greater than parent - data parent is what 6,000 6,000 - data is what 65 67 is greater than 65 s condition true so then we are connecting to right side so 8,000 devalue we are connecting here so this is connected so suppose if it is a lesser value very simple else block else block here it is else block right simply in a else block in a else block so we are just writing a value we are storing into air into left we are storing into pair into left this is simply so whatever the T value is there just consider instead of a 67 we are taking 6363 is less than the 65 so then by that time the node we should connect to the left side because it is a lesser value now it is a greater value in this example okay if it is a lesser value then connected to left side as it is a greater value here we are connecting to right so this is the insertion process so if you want to insert first we and we need to find out so what is the parent node to insert the new node and after finding the parent node where we have the insert to left side or to right side we need to connect them if it is a greater value than parent we should connect it to right side if it is a lesser value than parent we should connect it to left side simple thing okay so this is the insertion process in a binary search tree okay in the next session we will see right how to delete it right how to delete a node from the binary search tree okay for more videos please subscribe to nourish 80 channel thank you thank you all

Channel: Naresh i Technologies

Views: 226,720

Keywords: Data Structures, Naresh IT, Srinivas, Learn Data Structures, Hands on Data Structures Training, Data Structures Demo, Online Data Structures Training, Data Structures Tutorial Videos, Data Structures Overview, Data Structures Interview Questions

Id: bCtmP8pSBF4

Length: 21min 39sec (1299 seconds)

Published: Wed Oct 19 2016