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.
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.
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
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.
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 :)
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.
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.
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
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.
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?
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))
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.
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 ruclips.net/video/_pnqMz5nrRs/видео.html
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~
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).
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?
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)
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.
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
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 !
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: ruclips.net/video/azupT01iC78/видео.html
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.
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.
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!
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?
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.
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?
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.
karthik mohan Hi Karthik, the 'value' is compared to 'cur_node.value' rather than simply 'cur_node' because 'cur_node' is an instance of the 'node' class and not actually a value itself. If we want to access the value within the node object we have to use the dot operator. If you have any further questions please let me know!
Brian Faure Thanks! But I don’t get it. How “cur_node” becomes an instance of “Node class” when it is actually present in the “Binary_search_tree” class? When accessing the “value (instant attribute)” from the node class using dot operator as “cur_node.value” does python implicitly consider it as an instance of node class without any additional declaration?
karthik mohan All nodes in the tree are declared as instances of the node class either in the insert or _insert functions. If you look at the first case where we enter the _inset function, the cur_node will be equal to the self.root, because it is passed this value from the insert function, and of course self.root, if not None, is an instance of the node class. All other nodes are declared as node objects from later on within the _insert function. Hopefully this clears it up a bit.
Brian Faure Okay... so the key line is from the insert function “self.root=node(value)”. So for the first step of _insert the self.root becomes the cur_node and it is thus nothing but an instance of the node class as “self.root=node(value)”...whose attribute (value) is accessed using a dot operator. Is my understanding right?
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?
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.
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!
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.
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 ).
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.
Firstly, Thanks for the beautiful videos. You are the best!!. I have a question, In _insert method, why can't we handle duplicates. Doesn't binary search tree insert the values equal to the current node to the left. In that case, can't we just have the first "if" condition as
It just depends on the specific implementation, some BSTs might put equal values to the right and some to the left, in this case I decided to omit equal values for simplicity. Without actually running it myself, I don't think there would be any issues if you used
Thank you so much, this is amazing. Only have one question: I want to traverse ALL nodes that are under a SPECIFIC node that is specified by user. I know I can use the height method as an example, but I can't comprise the logic necessary to return every single value under a specific node. Any help with that?
My answer might be too late. It is pretty simple to do that. you can use the search function on the tutorial and once you found the target node, you can use the *pointer* that has that value and pass it as a parameter to the _print_tree function. It will print you all the leaves of that node including the target node.
Hello Brian I wanted to ask what does line 68 do? “ tree = binary_search_tree() “ I typed the code exactly how you typed it for practice and shows it’s an undefined name. I’m coding on Python 3.6 Thanks!
Hey Matt, "tree=binary_search_tree()" will set the 'tree' variable equal to a newly created instance of the binary_search_tree class, if this isn't working for you make sure that you named the class 'binary_search_tree'. If you did, feel free to share your code on repl.it and I can take a look for you.
Yes its still not working for me, even after changing variables and class names. Heres my code: repl.it/@miglesias4/ProductiveRawQuadrant Thank you for taking the time to assist me much appreciated!
Okay, I think I fixed the issue you were having repl.it/repls/ShockingClientsideTutorial , the problem was that in your 'init' functions you only had a single underscore '_' on each side of 'init' whereas, to declare a Python class constructor you need double underscores '__'. I also removed the first 'self' parameter from your recursive calls to _insert because you don't need to specify 'self' when calling a class member function, only when defining it. There were some other minor naming issues I fixed up so it should be working now.
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
def insertTree(self, data): if self.root is None: self.root = Node(data) else: self.insertHelper(self.root, data) def insertHelper(self, start, data): if start is None: start = Node(data) print(start.data, "added successfully") else: if data
After searching thousand of videos at ytb, this tutorial is the most helpful and insightful! thanks!
@@chloeliu9207 Awesome news! Happy the video helped you ✌️
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.
Best walk through implementation of BST on RUclips by far! Thank you so much.
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.
The sound at 7:39 super motivating... and the energy level from 7:25-7:40 is just threw threw the roof.
Fantastic video and great explanations. Rarely comment but please keep this up
Such an underrated channel
Thank you, helped me finish my homework without losing my mind x'D
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
Finally! I undertand BST! Thanks a lot for yoru help
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.
I agree, Two classes is the way best way to implement any non linear data structure!
Thanks for this! I was having trouble understanding my professor when we learned this today.
very good explanation of binary search trees. straight to the point. explained each of the parts very well. thanks a lot!
Thank you for being clear about the values on the left and right side of the tree. Very helpful detail.
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 :)
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.
awesome video! in the function ` fill_tree`, you don't need to return tree, it does it "inplace"
Part 2 (deletion) of the Binary Search Tree lesson can be found here: ruclips.net/video/Zaf8EOVa72I/видео.html
best binary tree tutorial ever!
Fantastic video~ You're the first person that has explained this in a way that makes sense!! THANK YOU
Best video and code I've seen on this and I've been looking for weeks! Thank you!
7:39
lmao
A wild Fart Spotted
ha
Thanks a lot Brian, I was actually looking for this. Well explained.
easy to understand and pretty well summed up the BST. thanks :)
Thanks for watching!
Very concise and informative! Thanks man
THANKS my guy) Definitely deserve the recognition)
Superb explanation and coding.Helped a lot.Thanks Brain
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.
I observed this too, or you can start with -1 instead of zero
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
Amazingly explained!! Hats Off
could you please explain me a little bit more about _print_tree(self, cur_node) function?
Excellent explanation! Great work!
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
thanks for the video! well explained, good pace
Nice video! Expecting to see the deletion part of BST :D
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.
Brian Faure I'm so appreciate :D Thank you for your effort on these nice videos
Just finished the video covering the deletion function: ruclips.net/video/Zaf8EOVa72I/видео.html , thanks again for the kind comments!
Thank you! I have watched it immediately :D Looking forward to your following videos!
Very clear since I am coming from Java.
Fantastic video, can be understood quickly :)
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.
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?
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))
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.
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 ruclips.net/video/_pnqMz5nrRs/видео.html
Thank you so much!
Can i add the new root value at the binary_search_tree __init__
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~
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).
No. It’s a snake to mouth paradigm. You’ll get it after much practise suqqing on knobs and snake heads.
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?
32 minutes of yt video (this) = Better_than(My_asd_classes) + Understanding
Very good explanations. Much appreciated!
Do you have video in Graph a nd algorithm
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)
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.
Thanks Brian for the wonderful explanation
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
had to set in class node that self.value = value and not None it was overwriting my values in the node constructor
Amazing explanation, very nice!!
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.
Thanks! Sure thing, I'll do a vid on the different traversal methods and build off the BST code from this video.
@@BrianFaure1 I want to see these videos. Where are they?
This is a great video! Did you ever make a video on the different traversals? If not, it would be cool to see one.
Hi Vanessa, unfortunately I haven't yet gotten around to making that but it is on the queue. Thanks for watching!
Excellent explanation! Thank you!
fantastic explanation! Thanks again.
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 !
Great explanation sir..
Great tutorial
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!
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: ruclips.net/video/azupT01iC78/видео.html
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.
please make a video on Hashtable with linear probing
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.
in the insert function , in else block why is there a '_' before insert ?? are we just calling the insert recursively?
Really helpful thankyou
thank you so much for the explanation
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.
this is just awesome..sir thanks
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.
No need to BST, you don't sort elements. Hashing does fit here actually
Great video man very useful!
@Brian Faure ,in an interview do you recommend to follow your approach , I mean break in two functions. Thanks
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!
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?
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.
@@BrianFaure1 Thanks Brian
nice video, i am not able to understand how does the display method work. can you please explain that ?
The way this guy doesn't put spaces around commas and equality operators drives me nuts
Great tutorial, thanks a ton!
great video man .. thumbs up from me
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?
ah, just realize 'Value already in tree' comes from insertion, not printing
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.
excellent video, very informative
Thanks Rakhee!
Thank You Brian
Can someone please tell me why it’s “value
karthik mohan Hi Karthik, the 'value' is compared to 'cur_node.value' rather than simply 'cur_node' because 'cur_node' is an instance of the 'node' class and not actually a value itself. If we want to access the value within the node object we have to use the dot operator. If you have any further questions please let me know!
Brian Faure Thanks! But I don’t get it.
How “cur_node” becomes an instance of “Node class” when it is actually present in the “Binary_search_tree” class? When accessing the “value (instant attribute)” from the node class using dot operator as “cur_node.value” does python implicitly consider it as an instance of node class without any additional declaration?
karthik mohan All nodes in the tree are declared as instances of the node class either in the insert or _insert functions. If you look at the first case where we enter the _inset function, the cur_node will be equal to the self.root, because it is passed this value from the insert function, and of course self.root, if not None, is an instance of the node class. All other nodes are declared as node objects from later on within the _insert function. Hopefully this clears it up a bit.
Brian Faure
Okay... so the key line is from the insert function “self.root=node(value)”. So for the first step of _insert the self.root becomes the cur_node and it is thus nothing but an instance of the node class as “self.root=node(value)”...whose attribute (value) is accessed using a dot operator. Is my understanding right?
karthik mohan Exactly
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?
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.
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!
Not related to data structures but can you please do a Github tutorial video? Thanks!
Video on segment trees,Fenwick trees...
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.
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 ).
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.
Thanks for this video.
i am getting an error AttributeError: 'binary_search_tree' object has no attribute '_print_tree' please help me in this one
it is at line no - 38 please help me out
Thank you so much sir
the fast forward sounds now reminds me of animal crossing XD
Firstly, Thanks for the beautiful videos. You are the best!!. I have a question, In _insert method, why can't we handle duplicates. Doesn't binary search tree insert the values equal to the current node to the left. In that case, can't we just have the first "if" condition as
It just depends on the specific implementation, some BSTs might put equal values to the right and some to the left, in this case I decided to omit equal values for simplicity. Without actually running it myself, I don't think there would be any issues if you used
Thanks!!
Excellent, thanks!
Thank you so much, this is amazing.
Only have one question: I want to traverse ALL nodes that are under a SPECIFIC node that is specified by user. I know I can use the height method as an example, but I can't comprise the logic necessary to return every single value under a specific node. Any help with that?
My answer might be too late. It is pretty simple to do that. you can use the search function on the tutorial and once you found the target node, you can use the *pointer* that has that value and pass it as a parameter to the _print_tree function. It will print you all the leaves of that node including the target node.
@@josephnke9324 2 years late mate
this is really helpful...
Hello Brian I wanted to ask what does line 68 do? “ tree = binary_search_tree() “ I typed the code exactly how you typed it for practice and shows it’s an undefined name. I’m coding on Python 3.6
Thanks!
Hey Matt, "tree=binary_search_tree()" will set the 'tree' variable equal to a newly created instance of the binary_search_tree class, if this isn't working for you make sure that you named the class 'binary_search_tree'. If you did, feel free to share your code on repl.it and I can take a look for you.
Yes its still not working for me, even after changing variables and class names. Heres my code: repl.it/@miglesias4/ProductiveRawQuadrant
Thank you for taking the time to assist me much appreciated!
That link seems to be broken, getting a 404 when trying to go to it.
This one should work: repl.it/@miglesias4/BinarySearchTree
Okay, I think I fixed the issue you were having repl.it/repls/ShockingClientsideTutorial , the problem was that in your 'init' functions you only had a single underscore '_' on each side of 'init' whereas, to declare a Python class constructor you need double underscores '__'. I also removed the first 'self' parameter from your recursive calls to _insert because you don't need to specify 'self' when calling a class member function, only when defining it. There were some other minor naming issues I fixed up so it should be working now.
great explanation!
Thanks Arthur!
Historically BST right node uses ">=," allowing for duplicate keys.
tree.print_tree() in python3. took me a half hour figure out why it wasnt printing out.
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
Adherence to PEP 8 would definitely make it clearer!
@@rockstarjazzcat Absolutely
thanks @BrianFaure.
Why are you creating 2 classes
What kind of keyboard do you use?
corsair k65 rgb with Cherry red keycaps :)
@@BrianFaure1 They sound great :)
def insertTree(self, data):
if self.root is None:
self.root = Node(data)
else:
self.insertHelper(self.root, data)
def insertHelper(self, start, data):
if start is None:
start = Node(data)
print(start.data, "added successfully")
else:
if data