Python Data Structures #5: Binary Search Tree (BST)

[@BinaryAdventure]

Yeah I've watched a lot of these. This video really helped me to re-grasp the concept well; it's hard to put into words but you are well-spoken and direct, which I learn best from. You do not ramble and wander in your presentations which is helpful for technical subjects.

[@chloeliu9207]

After searching thousand of videos at ytb, this tutorial is the most helpful and insightful! thanks!

[@BrianFaure1]

@@chloeliu9207 Awesome news! Happy the video helped you ✌️

[@nackyding]

Best walk through implementation of BST on KZbin by far! Thank you so much.

[@nancycarlson548]

So yes, please make a delete node video. What is great about your approach is your commentary as you are writing the code. This is sooo helpful to those of us who are still learning how to write the code as it connects to the logic of the data structure. This teaching technique is hard to find! Please keep this up and thank you.

[@BrianFaure1]

Part 2 (deletion) of the Binary Search Tree lesson can be found here: kzbin.info/www/bejne/kJLJaXiFi8ZqaKs

[@333robel]

The sound at 7:39 super motivating... and the energy level from 7:25-7:40 is just threw threw the roof.

[@chaoticpringle2578]

Thanks for this! I was having trouble understanding my professor when we learned this today.

[@davidarthurpaul]

Fantastic video and great explanations. Rarely comment but please keep this up

[@HarveyXE]

Thank you for being clear about the values on the left and right side of the tree. Very helpful detail.

[@boohoo334]

Such an underrated channel

[@fredesch3158]

Really nice, I was really stuck at how to start implementing, when I saw the use of 2 classes one for the node and one for the tree itself everything just clicked, I coded and it worked, THANK YOU SO MUCH, I always need a jumpstart to make my brain work and your video was just perfect.

[@shreehari2589]

I agree, Two classes is the way best way to implement any non linear data structure!

[@jennaalden3658]

awesome video! in the function ` fill_tree`, you don't need to return tree, it does it "inplace"

[@autismo1969]

very good explanation of binary search trees. straight to the point. explained each of the parts very well. thanks a lot!

[@Samuel-lm1wb]

Thank you! very helpful, watched like idk 6 or so videos on youtube but they were mad confusing especially on the recursion part. You were clear thank you

[@Abhi-qi6wm]

def insert(self,data): if self.root: self._insert(data,self.root) else: self.root=node(data) def _insert(self,data,curr_node): if curr_node is None: curr_node=node(data) return curr_node if datacurr_node.data: curr_node.right=self._insert(data,curr_node.right) else: print( 'Value already exists') return None return curr_node Implemented a shorter version of the insert method :)

[@carlavirhuez4785]

Finally! I undertand BST! Thanks a lot for yoru help

[@vishesh_soni]

Very Nice and clean Code. You know I was thinking of making DS&A with python videos on youtube coz I couldn't find any. But now I have seen way better than I expected.

[@MCNeko6554]

Thank you, helped me finish my homework without losing my mind x'D

[@zakiahmedqureshi4358]

easy to understand and pretty well summed up the BST. thanks :)

[@BrianFaure1]

Thanks for watching!

[@karthikudupa5475]

Thanks a lot Brian, I was actually looking for this. Well explained.

[@akizzlebrand4657]

Best video and code I've seen on this and I've been looking for weeks! Thank you!

[@wojohn6441]

best binary tree tutorial ever!

[@alexsugarman9511]

For your insert method, I would change the parameter to *args. That way you can input one, or multiple values with one insert command from your main. You just have to iterate through the args first

[@natalieweishuhn521]

Fantastic video~ You're the first person that has explained this in a way that makes sense!! THANK YOU

[@wenchehsu8915]

Nice video! Expecting to see the deletion part of BST :D

[@BrianFaure1]

Haha sorry about that, I'll be coming out with a video on it soon! I'll reply again to your comment again once it's released.

[@wenchehsu8915]

Brian Faure I'm so appreciate :D Thank you for your effort on these nice videos

[@BrianFaure1]

Just finished the video covering the deletion function: kzbin.info/www/bejne/kJLJaXiFi8ZqaKs , thanks again for the kind comments!

[@wenchehsu8915]

Thank you! I have watched it immediately :D Looking forward to your following videos!

[@RaniLink]

You find the tree's height much simpler with: _height(self, current_node): return -1 if current_node is None else 1+max (self_height(current_node.left), self_height(current_node.right))

[@bright1402]

Very concise and informative! Thanks man

[@yaseen1478]

7:39

[@BrianFaure1]

lmao

[@GurfatehSinghDhaliwal]

A wild Fart Spotted

[@Draco-pe4fg]

ha

[@arturfil]

Excellent explanation! Great work!

[@joshiravishankar]

Fantastic video, can be understood quickly :)

[@jasonzhang6534]

thanks for the video! well explained, good pace

[@azizas9366]

Very clear since I am coming from Java.

[@ankittank2098]

Amazingly explained!! Hats Off

[@nikitaizmaylov4888]

THANKS my guy) Definitely deserve the recognition)

[@lilysu2529]

the fast forward sounds now reminds me of animal crossing XD

[@ardsnijders7777]

one small thing I ran into; at one point you define the fill_tree function, pass in the Tree object and re-assign the output to variable tree. However, (In my implementation) doing so reset the type of tree from to which rendered me unable to perform the tree.print_tree() method.

[@brianwahome5789]

You are a God!! Mind doing a BST validator too? Also it would be great having access to the repo you post this Code in. Thank you so much!

[@BrianFaure1]

Thanks Brian! I've just posted the code here: github.com/bfaure/Python_Data_Structures/blob/master/Binary_Search_Tree/main.py , it also contains the logic for the deletion function which isn't covered in this video. Thanks also for the recommendation, I'll definitely do a BST validator ASAP. Edit: BST Validator lesson can be found here: kzbin.info/www/bejne/l6vYoYdmZs52bZo

[@rwothoromoelijah]

Very good explanations. Much appreciated!

[@shrikantkarki4966]

Superb explanation and coding.Helped a lot.Thanks Brain

[@darkseeven]

32 minutes of yt video (this) = Better_than(My_asd_classes) + Understanding

[@ManaNoodles]

The way this guy doesn't put spaces around commas and equality operators drives me nuts

[@siddharthadas86]

fantastic explanation! Thanks again.

[@wahtsfgsgwwwsxq]

Excellent explanation! Thank you!

[@marco.nascimento]

Amazing explanation, very nice!!

[@ashwinimandani2829]

Great explanation sir..

[@VibhaDhar]

Great video! I have followed your linkedList video also. The code is clean and easily understandable. Can you please plan on adding DFS and BFS also.

[@BrianFaure1]

Thanks! Sure thing, I'll do a vid on the different traversal methods and build off the BST code from this video.

[@lenaerbs8359]

​@@BrianFaure1 I want to see these videos. Where are they?

[@AnilYadav-ut5zj]

For the _height() function, shouldn't you return cur_height -1 because even if its None, you have already incremented current height by 1 via the recursive functions.

[@TheSSB007]

I observed this too, or you can start with -1 instead of zero

[@rizkifitrarrijal9138]

thank you so much for the explanation

[@sifagayev7793]

Great tutorial

[@EnglishRain]

Great tutorial, thanks a ton!

[@JoaoCfgc]

Great video man very useful!

[@rakheekulkarni2708]

excellent video, very informative

[@BrianFaure1]

Thanks Rakhee!

[@AbhishekSingh-cx5dr]

this is just awesome..sir thanks

[@subashchandrapakhrin3537]

Thank You Brian

[@mrhobojim6098]

Really helpful thankyou

[@ayeinsayali1340]

great video man .. thumbs up from me

[@burakhanaksoy]

Brian, another amazing video!! I want to ask a question though. What is the main reason you portion a function to private and public? Just want to understand the logic behind. Thanks for the tutorial~

[@fredesch3158]

I'm not the creator, but as far as I understood the private function takes as an additional parameter the node to analyze, the public one assumes the beginning of the tree (or the root of the tree).

[@tibettenballs4962]

No. It’s a snake to mouth paradigm. You’ll get it after much practise suqqing on knobs and snake heads.

[@daliacruz759]

This is a great video! Did you ever make a video on the different traversals? If not, it would be cool to see one.

[@BrianFaure1]

Hi Vanessa, unfortunately I haven't yet gotten around to making that but it is on the queue. Thanks for watching!

[@djuka8121]

could you please explain me a little bit more about _print_tree(self, cur_node) function?

[@nicknaik]

Excellent, thanks!

[@rockstarjazzcat]

Historically BST right node uses ">=," allowing for duplicate keys.

[@RomanMamedov333]

Thanks for this video.

[@johndu9255]

Hi Brain, I met a problem with this code, the "search" function does not return "True" when the number was generated by the "Random function", but inserted number is fine. do you have any idea about this? Thank you !

[@utkarshpol123]

when in search I search for a number which is not in the list instead of false it shows an error saying non-type attribute value

[@isha6510]

If we only want to write the left view of the tree then how can we do it . I mean with print function when i tried to print only the right part of the tree it worked properly but for the left it's not working. Can you please help me?

[@gokulraviteja5209]

Video on segment trees,Fenwick trees...

[@indominus9184]

please make a video on Hashtable with linear probing

[@kajalmondal9745]

Thank you so much sir

[@shibajichatterjee3190]

Thanks a lot for the tutorial. Can you please make a video on creating a Huffman tree., as that is a binary three we create from the leaf to the root ( from below), I am having a hard time figuring out implementing the algorithm.

[@jojoesekyisagoe]

I guess you dont need to check if self.root == None in the height function since the recursive call takes care of a None condition. you can just have "return self._height(self.root, 0)" as the only line in the height function.

[@rahularvindshinde]

this is really helpful...

[@vincentluong6238]

Needs more views

[@neuralnets6656]

Can you demonstrate the code for the case where value == cur_node? Currently, you are printing "Value already in tree" - can you demonstrate the code to handle duplicate values by replacing the cur_node with value? Thanks.

[@arthurzhang7868]

great explanation!

[@BrianFaure1]

Thanks Arthur!

[@mykinvincible]

nice video, i am not able to understand how does the display method work. can you please explain that ?

[@animeknowledge8381]

Using Python 3.8 so may be the reason but it is just calling the place in memory and not the value at the pointer so im getting a typeError when calling value

[@animeknowledge8381]

had to set in class node that self.value = value and not None it was overwriting my values in the node constructor

[@rohitkumarj632]

How to store the tree created permanently even after closing the file. And also on fetching the tree and updating, the updates must also be saved.

[@nernaykumar8334]

i am getting an error AttributeError: 'binary_search_tree' object has no attribute '_print_tree' please help me in this one

[@nernaykumar8334]

it is at line no - 38 please help me out

[@BL-om2hn]

22:46 Hi Brian, could you give a more detailed explanation for the recursive part of the _height function. Like what will the left.height and right.height return if the cur.height of the left.height or right.height are not None yet.

[@BrianFaure1]

Hi Bowen, I'll explain using the following line identifiers (A,B,C,D)... (A) > if cur_node==None: return cur_height (B) > left_height=self._height(cur_node.left_child,cur_height+1) (C) > right_height=self._height(cur_node.right_child,cur_height+1) (D) > return max(left_height,right_height) Line A is essentially the base case of this recursive function, once we hit the child of a leaf node (which will equal 'None') we return the total height we've accumulated across the recursive calls, 'cur_height'. In line B we are starting a new recursive branch that will retrieve for us the height of the left sub-tree of 'cur_node', and similarly, in line C we start a new recursive branch to return the height of the right sub-tree of 'cur_node'. In line D we return the greater of the two heights, because the height of a node is defined as the longest distance from that node to a leaf node. It may be easier to understand if you realize this function will be called exactly once for each node in the tree (plus the 'None' children of leaf nodes), and the recursive calls would basically trace out a depth-first search of the tree, though we don't search for values rather we simply add to our found height. In lines B and C, the reason we pass cur_height+1 as the second parameter to the _height function is that we must increment our height value by one because we are traversing down to the next level in the tree. Let me know if this cleared it up at all or if you have any further questions. If you're interested, a resource that helped me understand this function in more depth was this great tutorial by mycodeschool kzbin.info/www/bejne/laHRooCwatOliNU

[@BL-om2hn]

Thank you so much!

[@jingyuchang1885]

Thank you very much Brian!! Really good video! I noticed in your code which you posted in github is actually not the same as the code in the video. You added parent pointer in github. You used the parent pointer in insert function and deletion function. I wonder is there any advantage to have the parent point? Or it's just easy for the deletion function?

[@BrianFaure1]

Hi Jingyu, the parent pointer is mostly just to simplify the deletion function. When we delete a node we need to alter the parent (so it no longer points to the node we wish to delete) and if we didn't include a parent pointer we would need to traverse through the tree to find the parent before we could actually perform the deletion, which could take a while if our tree was fairly large. The parent pointer is also involved in the insertion function but all we do there is set it correctly when we insert a new node. I explain it a bit more in the deletion video but when we call delete_value (which is a passed a value in the tree) we still _do_ have to traverse through the tree to find the node with that value, so the parent pointer only really increases the efficiency of the 'delete_node' function.

[@jingyuchang1885]

Thank you very much Brian! You explained very clear! I literally wrote down every single word you said in the videos as notes cause my native language is not English. Sometimes I need to read the notes again after the video to make myself really understand! You videos really helped me a lot! I will watch all your videos and hope you will make more videos!! Thanks again!

[@kritiohri2950]

Hi Brian..just as we are printing the value of current node or the root (print(str(cur_node.value))) , where are we printing the values of left and right child?? Only call is being made to the fucntion (self._print_tree(cur_node.left_child)) and self._print_tree(cur_node.right_child)

[@BrianFaure1]

Hi Kriti, the left child will be printed before the cur_node and the right child will be printed after... > self._print_tree(cur_node.left_child) # this will print the left_child (if not None) > print str(cur_node.value) # this will print the cur_node > self._print_tree(cur_node.right_child) # this will print the right_child (if not None) ...and because it's handled by recursion, we don't need to specifically call 'print str(cur_node.left_child.value)' or 'print str(cur_node.right_child.value)', just passing both as parameters to the _print_tree function is enough. I hope that clears it up.

[@kritiohri558]

Thanks Brian for the wonderful explanation

[@tomporkka5273]

Thanks for this! Quick question, are the BST's at 00:44 and 01:28 valid or is that a typo? I'm confused by the left side where the child nodes of 7 are 2 and 6?

[@davidgutierrezarias3309]

@Brian Faure ,in an interview do you recommend to follow your approach , I mean break in two functions. Thanks

[@BrianFaure1]

Hey David, for interviews I think the best approach is whatever is easiest for you to code and, more importantly, to be able to explain. I doubt you would be asked to code an entire BST for an interview but it's certainly possible, more likely would be just a single function (insert for example). When it comes to coding during interviews it's hard to know how much the interviewer is expecting of you so while you're writing if you come to a point where it would make sense to call a function to perform some action (for example if you were moving an object across a screen and would call a function to perform the x,y coordinate transform) I would say certainly call the extra function, if you have time you can fill in the logic for that later on. It's definitely better to have the higher-level program correct vs getting stuck in the weeds trying to figure out some logic in the beginning, then never actually even finishing the high level logic. For the recursive functions we use in the BST here, you could either break it into two functions (as seen in the video) or use a single function that performs all the stuff of the non-recursive function only on the first iteration (so you would need some sort of variable to check to see if you're on the first iteration or not), in this case I think breaking it into two functions makes sense but I'm sure many programmers would disagree. Good luck with the job hunt!

[@jimmyshenmusic]

Super nice video. I love your code of the BST. It will be good if the code is posted online. Also, for the private method, name is under the double underscore will also work, right? I found the lib of python is using double underscore for all the private functions.

[@BrianFaure1]

Hi Jimmy, thanks for the nice comment! The code for this video can be found here: github.com/bfaure/Python_Data_Structures/blob/master/Binary_Search_Tree/main.py . Using a single underscore is more of a Python style convention than anything, it basically tells anyone using the code that they should refrain from calling the function directly (essentially making it a private function of the class, as you say) but doesn't enforce this in any way. A double underscore function or variable is actually treated slightly differently by the Python interpreter. I found a good answer on stack overflow talking about this exact thing ( stackoverflow.com/questions/1301346/what-is-the-meaning-of-a-single-and-a-double-underscore-before-an-object-name ).

[@jimmyshenmusic]

Thanks for the sharing of the code. Also thanks a lot for the link provided on the explanation of the difference of the double underscore and single underscore. It is very clear. Thanks.

[@-mwolf]

thx really helpfull

[@oishikachaudhury3718]

Not related to data structures but can you please do a Github tutorial video? Thanks!

[@avhishekbiswas4251]

in the insert function , in else block why is there a '_' before insert ?? are we just calling the insert recursively?

[@nidhi12mishra]

How many times did you guys have to watch this video to finally understand it thoroughly. ? Bcz once is not enough for me.

[@aadisheshsharma1911]

If you're theoretically sound enough, you're good to go. :)

[@clairelolification]

10 times

[@adeolaogunleye7965]

Can i add the new root value at the binary_search_tree __init__

[@jodog31]

tree.print_tree() in python3. took me a half hour figure out why it wasnt printing out.

[@mahyarsedigh6203]

when _search called recursively, doesn't it check the value first and if it is equal to what we are looking for it should return True; I am confused in your first run you got False False; why you had to add return statement before each of those calls?

[@BrianFaure1]

Hi Mahyar! Yes it does return True if the current value is equal to what we're searching for but if its not it needs to recurse lower into the tree (in the recursive function calls). The issue with the first approach was that when we recursed into the tree we weren't propagating the return values back up the function stack i.e. if one of the lower search calls found True we wouldn't return that, we would continue to the bottom of the function and just return False. Please let me know if this makes sense.

[@mahyarsedigh6203]

@@BrianFaure1 Thanks Brian

[@rahadulislamrahat328]

Do you have video in Graph a nd algorithm

[@kirimi782]

thanks @BrianFaure.

[@pjcamiam]

Don't know how people are saying the style is clean when it could use quite a bit of help (please use more space out operators and operands), but otherwise nice implementation

[@rockstarjazzcat]

Adherence to PEP 8 would definitely make it clearer!

[@pjcamiam]

@@rockstarjazzcat Absolutely

[@pedrocastro882]

THANK YOU!!!!!!!!!!!!!!

[@irisx6619]

Hi, Any chance that you can explain how to take words from a paragraph in a text file and store them in the BST? Thanks.

[@ilkinaliyev1044]

No need to BST, you don't sort elements. Hashing does fit here actually

[@yuanyuan23191212]

Thanks for your video! I have a question. This tree at first is empty. Then how come it will return 'Value already in tree!' in the first line when printing the tree?

[@yuanyuan23191212]

ah, just realize 'Value already in tree' comes from insertion, not printing

[@zzobaer09]

thanks bro

[@Wonnnebju]

I like your sthoyl

[@saideepspeaks]

💥💥