BINARY SEARCH TREE (BST) AND ITS OPERATIONS - DATA STRUCTURES

[Music] hello friends welcome back to our channel so in the previous session we have seen the three traversals and how to construct a tree with the help of these camisoles techniques in this session we'll go with one more topic that is a binary search tree right this is called as a BST binary search string right so here it is also a dream it is also a tree and it should follow the condition of a binary tree so we know the difference between a tree and a binary tree so I'd written consists of in the tree a normal tree anymore with any node can have a number of children but a witness in a binary tree every node should have a and close to two children so that constraint should be followed by BST so here also every node should have at post two children that means it is a variant of a binary it is a variant of it so we can call it as a time okay so every node must have at most so this is very important you know one or two it was me and moves to two children right so that's why we call it is a variant of a binary tree that's a one thing second one is this is almost similar to or binary search so just recall the binary binary search so let us take in in the Mint's C so one condition while implementing this binary search means so before going to the binary search the elements should be in a sorted order so if they are not a sorted order the first we have to sort them and then we have to apply the binary search so if let us take these elements and what's the first attempt we are going to see in the binary search so so this is a binary search so first we will find that middle element we will find the middle element so that all the elements which are left to that are less then we will middle element all the elements which are on the right side those are greater than million if recursively we will find the same video element in the left left path and the same green element in the right path and based upon the middle element will just reduce the problem space so like this we'll apply this binary search the same thing will apply in the binary search tree also so here in this binary search tree this element will be consider as a root root node right this middle element will be considered as a root node and this will be considered as a left subtree and this will be considered as a right subtree right so again recursively in this left subtree will find the minimum we made that will be considered as a hoot and the left side is a left sub-tree right side is a right center similarly in this right in the right path we will again find the middle element we will consider that event as a hoot and the left left the path will be the left sub-tree the high part will be the right sub-tree and recursively we will call that so the same thing will apply for the tree construction so that is why we can say by using this binary search + binary tree we can form the BST right see so binary tree + binary search is nothing but our ministry by researched right so see that means all the elements all the elements of left subtree are less than root all the elements of as well left subtree must be less then must be less than hope not similarly all the elements from right subtree must be greater than only reversal right subtree must be rather than true all the elements of left subtree must be greater than poop right see if you consider some 15 let it be a 50 is in a root node so the left subtree should contain the less than 50 and the right subtree should contain greater than 50 see 40 60 right so this is a PhD because a node 50 is having the next announce right a left side rather than on right side next if you form this subtree again if you want to add a children to this 40 again we have to follow the same thing so for the 40 the left subtree of this 40 should be less than 40 and the right subtree of this party should be greater than 40 but not less than I mean but not greater than 50 see here if you observe this is all true though this is a loop so here we can apply 30 because 30 is less than 1 and here that should be greater than 40 right greater than 40 so if you place a 70 that is completely wrong because all the elements of left subtree so this is all the sub thing right this is all the separate all the evils of you have to separate must be less than root here root is 50 right here root is 50 so 40 is less than 15 current so 40 is a root 30 is less than 40 right 70 70 is greater than 40 the condition is true but the 70 is greater than 50 which is a root of this subtree so we can't insert this 70 here right the condition is here we can insert the element which is greater than the 40 but less than 50 we can insert a 45 here so hopefully this rule this is completely left sub-tree so we know that all the elements of the left subtree must be less than root so we can't insert an element which is greater than the root element next here also we can write so here we can write a 20 and here we if you write some 42 that is completely wrong because 40 is a good here so all the events are free subtree so this is a subtree of 40 this is a certain of 40 so all the inverse of subtree must be less a loop so all the elements of this subtree should be less than 40 so on the right side of this 30 it should be greater than bit but less than this root so 40 will be not accepted here so here we can insert a 35 we can assert a 34 it here also same thing so 60 so if you if you insert the 20 so the 20 is less than 60 condition is true but 20 is less than 50 also but so this is the subtree of the right subtree of load 50 so all the elements of this sub tree should be greater than 50 and if you write if 60 here you have to insert 55 we can insert a 55 which is a greater than 50 ans density and here you can go with this enemy right so hope you understood this with this thing so every element of left subtree must be less than the root so every iteration or every sub tree we have to follow these two things so all the elements of left subtree must be less than root all the elements of subtree must be greater than root right so this is how we will follow while constructing the binary search tree right so hope you understood without any problem nice so what are the operations that we can apply on this BST so operations so we know that first one is insertion inserting an element into the lid into the binary by a BST so how to insert an element so just by comparing the root element we can insert an element into the beast because we know that all the elements are in a sorted order that means based off of the root now we can find the position of the element while inserting an element so if the node is I mean if the element is greater than the rule then automatically the position of that particular element will be on the right side left side subtree if the the new element is less than the root root load then the position of that particular new element will be on the left subtree and coming to the left subtree again repeat the follower repeat the same process so by that way we can insert an element into the binary search tree next deletion so how to delete an element from the by in by the search tree so here we will go with the three concepts so deleting an element or deleting a node with zero children one children and two children right so we can how to delete an element with a zero children that is a leaf nodes so there will be no problem it is notice right so how to delete an element with a 1 children one child and the to chain because our BST is a variant of buying a binary tree so every node may have at most 0 to I mean it was two children so this is the deletion process will go one by one third searching process so searching the element in the be hasty so we'll get we find whether the element is available in this ministry or not so just is simply comparing the remotes so every input process will be related to the root similarly minimum value so how to find the minimum element from the VST by decision maxximum bro so finding the maximum element from the BST right so these are the operations we are going to see in the further sessions regarding this binary search tree right so we start here and if you are having any doubts regarding this introduction of by BST feel free to post your doubts in the comment section so that I will definitely try to clarify all your doubts and if you need address localizations like my sessions share my sessions with your friends and and don't forget to subscribe to our channel keep following thank you very much thank you

Channel: Sundeep Saradhi Kanthety

Views: 43,202

Keywords: sundeep, saradhi, kanthety, data structures, lists, stacks, queues, trees, graphs, primitive, non primitive, linear, non linear, linked lists, ds fundamentals, ds basics, nodes, structures, interview, placements, cse, parent, child, leaf node, sub tree, root node, tree terminology, TREES IN DATA STRUCTURES, strictly binary, complete binary, incomplete binary, full binary, binary trees, binary search trees, BST, BST BASICS, BST CONSTRUCTION, BST EXAMPLE, BST INTRODUCTION, binary search

Id: DU5g_dEbSyQ

Length: 14min 31sec (871 seconds)

Published: Wed Jul 24 2019