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.
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 :)
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.
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.
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))
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
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).
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: th-cam.com/video/azupT01iC78/w-d-xo.html
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?
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 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?
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.
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
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.
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.
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!
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
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 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.
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?
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.
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 th-cam.com/video/_pnqMz5nrRs/w-d-xo.html
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
![30 ชั่วโมงคนเดียว บนรถไฟชั้น 3 โซเวียต [Around The World Ep. 2]](http://i.ytimg.com/vi/MlE9boAVqDA/mqdefault.jpg)
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 TH-cam by far! Thank you so much.
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 :)
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.
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.
I agree, Two classes is the way best way to implement any non linear data structure!
Thank you for being clear about the values on the left and right side of the tree. Very helpful detail.
awesome video! in the function ` fill_tree`, you don't need to return tree, it does it "inplace"
very good explanation of binary search trees. straight to the point. explained each of the parts very well. thanks a lot!
Part 2 (deletion) of the Binary Search Tree lesson can be found here: th-cam.com/video/Zaf8EOVa72I/w-d-xo.html
Finally! I undertand BST! Thanks a lot for yoru help
Thank you, helped me finish my homework without losing my mind x'D
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.
best binary tree tutorial ever!
Thanks for this! I was having trouble understanding my professor when we learned this today.
Fantastic video and great explanations. Rarely comment but please keep this up
Such an underrated channel
easy to understand and pretty well summed up the BST. thanks :)
Thanks for watching!
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
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))
7:39
lmao
A wild Fart Spotted
ha
Thanks a lot Brian, I was actually looking for this. Well explained.
Very concise and informative! Thanks man
Best video and code I've seen on this and I've been looking for weeks! Thank you!
Very clear since I am coming from Java.
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
32 minutes of yt video (this) = Better_than(My_asd_classes) + Understanding
Great tutorial
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 the video! well explained, good pace
Great explanation sir..
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: th-cam.com/video/Zaf8EOVa72I/w-d-xo.html , thanks again for the kind comments!
Thank you! I have watched it immediately :D Looking forward to your following videos!
Superb explanation and coding.Helped a lot.Thanks Brain
Do you have video in Graph a nd algorithm
Amazingly explained!! Hats Off
Fantastic video, can be understood quickly :)
Thank You Brian
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 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?
Really helpful thankyou
could you please explain me a little bit more about _print_tree(self, cur_node) function?
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
Excellent explanation! Thank you!
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: th-cam.com/video/azupT01iC78/w-d-xo.html
Great tutorial, thanks a ton!
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.
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!
thank you so much for the explanation
fantastic explanation! Thanks again.
Can i add the new root value at the binary_search_tree __init__
Amazing explanation, very nice!!
Very good explanations. Much appreciated!
please make a video on Hashtable with linear probing
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?
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
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?
Thanks for this video.
@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!
Why are you creating 2 classes
nice video, i am not able to understand how does the display method work. can you please explain that ?
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
this is just awesome..sir thanks
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
great video man .. thumbs up from me
The way this guy doesn't put spaces around commas and equality operators drives me nuts
Fantastic video~ You're the first person that has explained this in a way that makes sense!! THANK YOU
THANKS my guy) Definitely deserve the recognition)
the fast forward sounds now reminds me of animal crossing XD
Great video man very useful!
Thank you so much sir
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!
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.
Excellent, thanks!
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.
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!
in the insert function , in else block why is there a '_' before insert ?? are we just calling the insert recursively?
great explanation!
Thanks Arthur!
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
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.
this is really helpful...
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.
Needs more views
Historically BST right node uses ">=," allowing for duplicate keys.
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
Not related to data structures but can you please do a Github tutorial video? Thanks!
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
What kind of keyboard do you use?
corsair k65 rgb with Cherry red keycaps :)
@@BrianFaure1 They sound great :)
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
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.
Video on segment trees,Fenwick trees...
thx really helpfull
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 th-cam.com/video/_pnqMz5nrRs/w-d-xo.html
Thank you so much!
💥💥
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!!
THANK YOU!!!!!!!!!!!!!!
thanks @BrianFaure.