Binary Search Trees in Python: Checking the BST Property

[@theodor320]

If you keep providing this quality content your channel will blow up! We at university taking these courses are having a tough time getting professors actually wanting to teach, so you're a perfect complement!

[@LucidProgramming]

Really thrilled to hear that! Thanks for your kind words, and I hope to continue to deliver valuable content. Cheers, and thanks again for watching!

[@stevenlobo6666]

I too have completed this entire playlist of 40 videos, and man it was amazing!!!. It was perfectly organised, clean, and the best part it was simple. Thank you so much. Would love to learn more Python from you.

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@prarabdh6295]

Completed 40 lectures just few days before my interview.. hope it helps me... THANKSSSSSS SIR.

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@sushanthreddydaram5207]

I have watched almost all the videos of this playlist. You have done such a great job and I wanna thank you for helping me out with the Data Structures.

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing! I really appreciate the support, and if you want to support the channel, I do have a PayPal link paypal.me/VincentRusso1 for donations that go directly to the creation of content on this channel. I hope that the content I provide there will enhance the videos on my KZbin page. bit.ly/lp_email

[@joycejeyaratnam433]

@@LucidProgramming Hi, can you please make a video showing us how to delete nodes in BST? Thanks!

[@LucidProgramming]

@@joycejeyaratnam433 There is a Patreon page here that you can check out for making such requests. Cheers! www.patreon.com/lucidprogramming

[@basedworldsk8]

This series is really great I appreciate how concise and articulate you're at explaining this concepts.

[@LucidProgramming]

Thanks! Very much appreciated! :)

[@nikhilj.206]

Wow. I was doing the educative.io course for DSA in python and searched for a doubt on youtube and randomly came across this channel. Great work.

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@jasoncole3253]

Man, great thank you, you have been better than my university professor on the topics covered so far and by far the best on the tube. I will check your Algorithms playlist now!

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing! I really appreciate the support, and if you want to support the channel, I do have a PayPal link www.paypal.me/VincentRusso1 for donations that go directly to the creation of content on this channel. I hope that the content I provide there will enhance the videos on my KZbin page. bit.ly/lp_email

[@cilpavincent3761]

Hi Vinnie, Just finished 40 videos and really enjoyed it! Let me share my implementation for BST property check: def BST_property_check(self,start,q= Queue()): if start: satisfied = self.BST_property_check(start.left) if not satisfied: print('not satisfied') return False if not q.is_empty(): ref = q.dequeue() if ref.data > start.data: print(ref.data,'**') return False print(start.data) q.enqueue(start) satisfied = self.BST_property_check(start.right) if not satisfied: print('not satisfied') return False return True

[@LucidProgramming]

That's great to hear! Thank you for sticking with it and for the kind words!

[@gabrielade775]

Finishing this playlist right now and you're really awesome man. Thanks a lot. Please do other structures. BFS, Graphs, etc. Thank you and God bless!!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@dangchinhle]

Thank you so much for this playlist, it has helped me both in getting used to Python and in understanding DataStructure.

[@LucidProgramming]

Very happy to hear that. Thanks for watching!

[@sarasalam1766]

I have Just finished the entire playlist. I would like to thank you so much for the great content.

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing! I really appreciate the support, and if you want to support the channel, I do have a PayPal link (www.paypal.me/VincentRusso1) for donations that go directly to the creation of content on this channel. I hope that the content I provide there will enhance the videos on my KZbin page. bit.ly/lp_email

[@mohamadrezamoradi8958]

Thanks for your great videos. I think your `_is_bst_satisfied` method will return incorrect result in some cases. The logic in the method is not correct. It is true that every sub-tree of a BST is also a BST, but if every sub-tree of a tree (T) is BST it does not essentially mean that the tree (T) is BST. Just look at your third example at 5:02. Your code return True for this tree (which is not a BST): 8 / \ 3 10 / \ 2 25

[@mohamadrezamoradi8958]

By every sub-trees of _T_ I mean every sub-tree *except* the _T_ itself

[@jackkohnjj]

Yeah, it's incorrect. OP doesn't seem to care though, as multiple comments have pointed this out.

[@supersammy00]

Yeah I found the same result. This method only checks immediate children nodes.

[@clwalker85]

should be able to insert into a queue with an in-order traversal, and then iterate through the queue to make sure every element is less than the next; recursive method needs a max parameter with every call, where max is the largest integer encountered in that subtree

[@Magmatic91]

One of the best playlist on DS with Python. I'd buy any course you offer. Thanks.

[@LucidProgramming]

Thank you kindly. If you enjoyed these videos and like this content, the folks at Educative have helped me put together a DS and algorithms courses that I'm quite proud of. If you'd like to give it a look, I'll go ahead and provided a link here: www.educative.io/courses/ds-and-algorithms-in-python Cheers!

[@gokusaiyan1128]

Completed the whole series !! enjoyable 💯💯

[@LucidProgramming]

Excellent. I'm thrilled to hear that you enjoyed it!

[@nitugupta5302]

Thanks for this awesome series !!!! Its really helpful for me . I completed all the 40 lectures in this series and I am really thankful to u for teaching such type of complex topic in this much easier manner. After learning from you I feel that it become my habbit to learn from you and I eagerly waiting for your next lecture on data structure

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@prakhar_pratyush]

First of all, Thanks a lot ! I finished the full 40 videos series and enjoyed with little frustration ;-) And i wanna ask you if you have any plan for Graphs, Hash .. etc Finally I will appreciate the serious reply you give to each serious comment. Thanks :)

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. I hope to be putting out more similar videos soon! Especially on graphs, etc.

[@karangothwal5296]

@@LucidProgramming Waiting

[@apoorvjain3937]

I had watched all videos of data structures playlist it was awesome!! Just waiting for more videos that covers graphs

[@LucidProgramming]

Thanks! You can feel free to make suggestions on my Patreon page. This would streamline what you want to see and also help to support my channel. www.patreon.com/lucidprogramming

[@__RohitDevar]

Completed all videos thank u very much sir🥰🥰

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@jakubrudy9372]

Awesome tutorials, thanks, it helped me a lot!

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@chukwuemekanwokedi4061]

thanx for the vids. would you be posting topics on graphs, tries, and hash table soon? if you can that would be appreciated

[@LucidProgramming]

Cheers. I'll be putting up videos soon. Subscribe and stay tuned. Thank you for watching! :)

[@amritmadhav5867]

Sir, Your tutorials and contents are awesome..

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing! I really appreciate the support. I hope that the content I provide there will enhance the videos on my KZbin page. bit.ly/lp_email

[@govindkeshari7953]

Great playlist.👍

[@LucidProgramming]

Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!

[@navyashreeu3833]

Bro is graph data structure is important for coding interview. If it is important than i please you to make the videos on it.because i searched all over at internet but i didn't found any explanation like you.so please make a video on it.🙏🙏🙏🙏

[@LucidProgramming]

I have a Patreon page where you can make suggestions like this. Please do so, and I'll get to making some videos!

[@navyashreeu3833]

@@LucidProgramming how to visit that page

[@navyashreeu3833]

@@LucidProgramming cant you do that video as much as faster you can.and cant you upload in you tube as much as faster as possible.

[@LucidProgramming]

@@navyashreeu3833 Link is here. Cheers! www.patreon.com/lucidprogramming/

[@navyashreeu3833]

@@LucidProgramming thank you. but also please make videos on graph data structure and its relevant algorithms as soon as possible. and upload it in your you tube channel please.

[@rahulthapa9170]

I do not normally comment but your videos helped me a lot so I could not resist. I learned that you had a house fire from the comment below. I hope everything will be back to normal in your life and you will start uploading the video again. Also, are you planning to do Videos on Machine Learning?

[@LucidProgramming]

Hi Rahul. Wow, I really appreciate that you took the time to comment, and that's fantastic to hear. Thanks so much for your well-wishes, and yes, the house fire has been a bit of a set back in the tail end of 2018. I'm still dealing with the aftermath of that, so my pace on making new videos has been a bit slow. I hope to kick back in full force when that's dealt with and continue making content. Regarding machine learning, this is definitely something I would like to do, and it's been on my list for a while. Thanks for your suggestion and for your comment! Cheers.

[@tapstothebeat]

Hi! Do you also have a video that discusses deletion from a BST?

[@LucidProgramming]

Yes, I do. Check the binary tree playlist! Cheers and thanks for watching!

[@HT-on5sk]

Just finished watching the entire playlist, what would you recommend as a logical progression? Looking forward to viewing more of your content!

[@LucidProgramming]

Hi HT. Thank you for the comment, I really love reading comments like this and to know that the time I spend on this is helpful :) Once you tackle the "data structures" playlist, I would move onto the "algorithms" playlist on my channel. Tag in some of the content under the "technical interview" playlist as well for good measure. I intend to continue to contribute to both of these playlists in the coming months, so stay tuned! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing! I really appreciate the support. I hope that the content I provide there will enhance the videos on my KZbin page. bit.ly/lp_email

[@wakatoxihaha9989]

Hi, thank you very much for the video. Actually, I am a little confused about the purpose of having both inorder_print_tree and is_bst_satisfied. are they two methods for checking? Moreover, I think the is_bst_satisfied failed to check the tree like the bottom one you showed on slides 30 or video 4:58. Am I correct? Thanks.

[@LucidProgramming]

Hi Wakato. The is_bst_satisfied is a function to ensure that the BST property of the tree is maintained. In order printing is used to print the nodes in order. Two different functions that accomplish and return different things. Pretty sure my code provides the correct response for the trees on the slides. If I'm wrong though, please provide an example and I will fix! Thanks.

[@wakatoxihaha9989]

@@LucidProgramming tree1= BST() tree1.root = Node(12) tree1.root.left = Node(3) tree1.root.right = Node(14) tree1.root.left.left = Node(1) tree1.root.left.right = Node(13) #print(tree1.inorder_print_tree()) print(tree1.is_bst_satisfied()) 12 / \ 3 14 / \ 1 13 in my running, is_bst_satisfied() will return true for this case....

[@LucidProgramming]

@@joaquinherreraramos2237 Indeed, thank you for confirming! :)

[@GopalaKrishnangk21894]

Thanks for the videos, it is so clear to understand. Would like to know are you going to upload Graph DS videos?

[@LucidProgramming]

No immediate plans, but it's on my list. Cheers, and thanks for watching!

[@shaheerzaman620]

As usual very good. Do you have any plan of doing a machine learning series?

[@LucidProgramming]

Hi Shaheer. Thanks for your comment. I do indeed plan on doing a series on machine learning. Currently, I do have something similar up on the channel which is a tutorial on natural language processing. You might be interested to check out that series if machine learning is something that interests you: kzbin.info/aero/PL5tcWHG-UPH0vSrpSUowSfcVjh1noEJtX Hopefully, I'll be getting around to filling that out more and putting some machine learning videos up soon. Thanks for the suggestion!

[@tabhashim3887]

Would this be the time complexity of this and why? To me it seems like it is O(n) because you are doing an in-order traversal.

[@chitranshusingh4844]

Will you include graphs in the playlist anytime soon?

[@LucidProgramming]

I hope to. Stay tuned and subscribe.

[@RaboundTeam]

Hi, do you think you'll eventually make a few videos on dynamic programming, or scientific packages like NumPy, SciPy, Pandas, etc? The way you teach algorithms/concepts is great so I look forward to more videos on more difficult/other topics from you.

[@LucidProgramming]

Hi TempestEX. I really appreciate that comment. Indeed, dynamic programming and the other libraries in Python such as NumPy, SciPy, etc. are definitely on my short list of videos to make. There are some other balls I'm juggling currently, but I hope to get to making these videos sooner rather than later. Thanks for your suggestion, and I appreciate your comment! Cheers.

[@0saptarshi]

Thanks a lot. Can you please add videos for graphs in python too? Your D.S playlist is awesome. Please add graphy theory too to make it complete.

[@LucidProgramming]

Sure, you can suggest videos to add on my Patreon here: www.patreon.com/lucidprogramming

[@Jani-911-ps5]

Awsome, finally i found the CORE fondation of programming ,thanks a lot LUCID PROGRAMMING, IT companys interview in mostly fire question on data structure and here is all awsome answer avalible ,again thanks

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing! I really appreciate the support. I hope that the content I provide there will enhance the videos on my KZbin page. bit.ly/lp_email

[@Jani-911-ps5]

@@LucidProgramming sure and lots of love from India 🇮🇳

[@nickhume758]

Does the following return True for you as well? Should it be False, since the node to the right of the root is less than the root? not_bst = BST() not_bst.root = Node(3) not_bst.root.left = Node(2) not_bst.root.right = Node(1) not_bst.is_bst_satisfied() True

[@ravitanwar9537]

hey vincent . can't we use the following approach . use an empty array and append the inorder traversal values from the tree into this array and then check if array is sorted or not . just considering this as a solution , i know that time complexity is likely to go higher in this one . ps. why have you stopped uploading videos ?

[@LucidProgramming]

Hi Ravi. You could do that and it would work. However, as you said, if complexity is something you want to optimize, it wouldn't be ideal. As for my upload frequency, I actually experienced a house fire and have been dealing with the aftermath of all that. It's been a slow process getting back to base level. I hope to be able to start uploading at the end of this year or the beginning of next. It's also been a very busy end of year! Thanks for checking though. I hope to get back to it soon! Cheers.

[@ravitanwar9537]

@@LucidProgramming holy shit man. I didn't know that. Just hang in there n times will change buddy. All the best for future..

[@LucidProgramming]

@@ravitanwar9537 Yeah, it's been an interesting past couple of weeks. Anyway, I appreciate the support! I'm taking things with a positive attitude and attempting to see the silver lining present in these situations. Anyway, that's the pragmatic way to approach these things. Cheers, and thanks for your concern!

[@VIKASKUMAR-bh5sj]

I just finished the playlist it was awesome..! please make a video on Trie data structure if possible.. please...

[@LucidProgramming]

I started taking requests on my Patreon page! www.patreon.com/lucidprogramming

[@jagdishwarbiradar1763]

Damm good playlist 👍

[@LucidProgramming]

I do offer tutoring and consulting. You can reach out to the email in the "about" section and I can provide to you my rates. Cheers!

[@jagdishwarbiradar1763]

@@LucidProgramming thanks for giving me you're prestigious time .

[@VikramKumar-tk6wg]

Sir if after the inorder traversal if we append the nodes.data in an empty list and after that applying a for loop for returning False if (i+1) node.data

[@LucidProgramming]

I'm not sure I understand what your approach is here.

[@lucasshaffer3079]

@@LucidProgramming He is suggesting that we do inorder traversal print. But instead of printing to the screen we append to a list or array. Then we loop through that array to check if each node value is ascending only.

[@LucidProgramming]

@@lucasshaffer3079 Thanks for the clarification. I don't believe this will add to the complexity. The recursive and iterative approach yield the same time complexity. I suppose appending to a list will now add linear space in proportion to the size of the list. Loop through again is additive, so the extra linear term here will not dominate the existing complexity. So I think the only thing you're adding here is extra space.

[@funkymunky8787]

The is_bst_satisfied method here is incorrect, as it doesn't account for a max/min of ancestors, just direct children. So a tree that violates the BST property with respect to its grandparent will be incorrectly determined to be valid.

[@rahls7]

I feel like this solution is incorrect. What happens when the left part of the binary tree is valid and the right is not? it would still return true, no?

[@LucidProgramming]

Hi Rahul. I believe it should still work fine, no? I would encourage you to try that use case in the code on my Github, or the code that you've been writing to go along with this video, and to see what happens. I'm not sure I see why that would throw it off, but if you find a broken case, let me know and I will update the code on my Github.

[@rahls7]

@@LucidProgramming Hey thanks for the reply. I did try it out. It fails for this particular BST. test = BST(10).insert(5).insert(15).insert(5).insert(2).insert(1).insert(22) test.left.right.right = BST(11). And similar test cases.

[@LucidProgramming]

@@rahls7 Hmm, I'm not sure I understand this use case. Also, I see you're inserting "5" twice. The binary search tree will only have one entry for 5, correct?

[@neelnair6525]

Hey man, thanks a lot for these videos. I had a doubt related to the above Solution. For the statement: return self._is_bst_satisfied(cur_node.left, cur_node.left.data), what happens when the function _is_bst_satisfied() does not return back anything? Does the entire return statement get ignored?

[@LucidProgramming]

No, the return is "None" in that case.

[@neelnair6525]

@@LucidProgramming oh okay. But in that case, suppose a parent node has both left and right nodes, and the left node returns None to the parent node. Then because of the return statement in the parent node, it would return None to its PARENT without checking the BST property for the right node.

[@LucidProgramming]

@@neelnair6525 But the bst property functions return booleans, right? So I don't think that should be an issue. Might be missing something in your question.

[@VenkatSanthoshh]

@LucidProgramming I absolutely loved your video and explanation but if you don't mind helping me by explaining what's going on with the return inside the is_bst_satisfied(self) method , especially the lines from 68 to 70 , I understood if is_satisfied is None return True, but not the next return statement ? "return False" at line number 68, what is that return for?

[@LucidProgramming]

That return False gets hit if the condition is not satisfied. The outer True is the "base case" in a way. Not sure if that makes sense, if not let me know. Cheers!

[@VenkatSanthoshh]

@@LucidProgramming okay I understood the return False part but what about the base case outer True? for instance, if self.root is not None then return True or is it just the return statement that returns once the whole method is executed?

[@LucidProgramming]

@@VenkatSanthoshh Right, if there is no tree, the bst is trivially satisfied.

[@VenkatSanthoshh]

@@LucidProgramming Awesome , thanks

[@LucidProgramming]

@@VenkatSanthoshh No problem! :)

[@B85046]

How do we get to your Github page to check the code of your tutorial?

[@miroslavdanilov902]

why you didn't make video about deleting a node from BST?

[@LucidProgramming]

Time constraints?

[@miroslavdanilov902]

@@LucidProgramming naah, I think false priorities...but great tutorials though.

[@LucidProgramming]

@@miroslavdanilov902 False priorities?

[@miroslavdanilov902]

@@LucidProgramming how did you decide to make a video about BST property testing over node deletion? Time constraints?

[@LucidProgramming]

@@miroslavdanilov902 I am making content for free in my own free time. Why are you taking issue with the fact that I happened to not have a specific video?

[@goncoco]

Can you do hash tables next pleeeease. I love your content

[@LucidProgramming]

My time has been very limited as of late, but stay tuned!

[@goncoco]

@@LucidProgramming niceeeee👌💪💪

[@LucidProgramming]

@@goncoco :)

[@stevenlobo6666]

I had a doubt Will the function. " is_bst_satisfied" work properly for the 3rd binary tree at 5:06

[@LucidProgramming]

Hmm, did you attempt to run the code on the tree and see if it provided the expected response?

[@stevenlobo6666]

@@LucidProgramming yes, but I don't get it how it works

[@LucidProgramming]

@@stevenlobo6666 You might have to be more specific. What is causing the confusion?

[@stevenlobo6666]

@@LucidProgramming Ok, in the 3rd binary tree at 5:06, the last right node satisfies the condition of being greater than it's parent node and also greater than the root node. But it's parent node is on the left of the root node. So it's not a BST. But when we use the function 'is_bst_satisfied', this will qualify as a BST, as there is no way of checking whether all nodes on left are smaller then root node and all nodes on right are greater than root node.

[@LucidProgramming]

@@stevenlobo6666 I just ran my code on that last tree you're referring to. It returns "False" as expected. The "13" node on the far left low branch is the reason is violates this property. You might want to check your code against mine on GitHub.

[@lukpisimoh]

Just to make sure, this algorithm's complexity should be linear, right?

[@LucidProgramming]

Yeah, time complexity would be linear for this approach.

[@mdarifulislamsourov6029]

peach be upon you. hope you are doing well. I want a favor. Can you please add graph data structure in this tutorial series?

[@LucidProgramming]

My time as of late has been quite limited, but I sincerely appreciate your viewership and support. It is definitely on my list, although I am not sure when I will have the time to get to making those videos. Hope you understand and thank you again for your kind words.

[@mdarifulislamsourov6029]

@@LucidProgramming no problem brother, take your time and take care. peach be upon you

[@diwakarpalanisamy1387]

Hello sir is there any video for deleting node (three case) in BST

[@LucidProgramming]

I believe I have a video on this on my channel.

[@NoorAli-uh4uq]

One question my _in_order function doesn't print None as the last node, I don't why?

[@vincentrusso6563]

Have you taken the code directly from my Github account? I believe it should.

[@NoorAli-uh4uq]

@@vincentrusso6563 no I just wrote but I will copy it from github. Thanks though.

[@LucidProgramming]

@@NoorAli-uh4uq Whoops, commented on my other KZbin account. Hate it when it does that. Anyway, yeah do what the other account mentioned :)

[@WeakCoder]

He's good but unfortunately underrated and that's why he has stopped uploading

[@LucidProgramming]

Hey.... :)

[@NoorAli-uh4uq]

So basically for BST all the nodes on the left are less than the root node likewise all the nodes on the right are greater than the root node.

[@vincentrusso6563]

Yep, that's the recursive property of a BST.

[@iraklisivsivadze5996]

First, I thought to point that your "_is_bst_satisfied" method is not quite right, but then I find out that tour gist is updated with the correct one. It's a little misleading, please point this on this on your video.

[@LucidProgramming]

The downside is, I'm not sure there is a proper way to do this with the video retroactively. I think KZbin had this functionality before, but then took it away, unfortunately. Thanks again for watching!

[@iraklisivsivadze5996]

@@LucidProgramming You can add an annotation link to the video. Keep it up, you have quite comprehensive tutorials there.

[@LucidProgramming]

@@iraklisivsivadze5996 Will do, and thanks! Thank you as well for the kind words!

[@wamiqueansari5199]

Hi, I am try to run below code in leet code, and used same logic as above. I don't understand why it's not working. Not able to figure out what the issue is: class Solution: def isValidBST(self, root: TreeNode) -> bool: if root: isValid = self._isValidBST(root) # print(isValid) if isValid is None: return True return False return True def _isValidBST(self, curr_node): if curr_node.left: if curr_node.left.val < curr_node.val: return self._isValidBST(curr_node.left) else: return False if curr_node.right: if curr_node.right.val > curr_node.val: return self._isValidBST(curr_node.right) else: return False

[@LucidProgramming]

I have no idea what isn't working about your code, you haven't given me any details as to why you think it's not working.

[@wamiqueansari5199]

Hi, Sorry!! Below are the details. Complete Code: # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isValidBST(self, root: TreeNode) -> bool: if root: isValid = self._isValidBST(root) # print(isValid) if isValid is None: return True return False return True def _isValidBST(self, curr_node): if curr_node.left: if curr_node.left.val < curr_node.val: return self._isValidBST(curr_node.left) else: return False if curr_node.right: if curr_node.right.val > curr_node.val: return self._isValidBST(curr_node.right) else: return False --------------------------------------------------------------------------------------------------------------------------- Above code gives correct output 'true' for the tree [2,1,3]. But it gives wrong output 'true' for the tree [5,1,4,null,null,3,6]. I debugged a lot and noticed that _isValidBST is not getting called recursively. For [5,1,4,null,null,3,6], root (5) is passed initially to _isValidBST. After this, node with value 1 is passed as curr_node.left exists, then as 1 has no left or right child the root node should again start executing from the place it has stopped, but it never continues. I hope it is clear now. Please help me with this.

[@pawanmandal8787]

sir please make a video on AVL tree and hashing

[@LucidProgramming]

It's on my short list. Stay tuned!

[@pawanmandal8787]

@@LucidProgramming sir please can you share deletion of node in binary tree

[@LucidProgramming]

@@pawanmandal8787 This is already on my playlist.

[@pawanmandal8787]

@@LucidProgramming there is no code of deletion of binary search tree

[@LucidProgramming]

@@pawanmandal8787 Yes there is.

[@jingfenghong2312]

Why does inorder_print_tree() outputs have None in the end?

[@LucidProgramming]

What do you mean by "has None in the end"?

[@jingfenghong2312]

@@LucidProgramming at 9:48, the output is 1 3 6 8 9 10 11 None, there is a "None" behind the 11

[@LucidProgramming]

@@jingfenghong2312 Ah, it just goes one further level down that it needs. You can add an earlier termination condition if you wish.

[@jingfenghong2312]

@@LucidProgramming Thank you so much

[@LucidProgramming]

@@jingfenghong2312 No problem, hope that helped!

[@arjunreddy3615]

Even for nodes(ones to the right) with data lesser than data of the root.. it comes out to be true... For example : 4(root),2(left),3(right).. Could you please adress this.. Even for 2,1,2 it is true

[@arjunreddy3615]

After removing the return statements in the helper function as below I got the correct answer for tree of level 1.. But for larger input levels that does not serve well.. I have gone through github code of yours and it works pretty well but was not easy to understand... code: def _is_bstSatisfied(self,cur_node,data): if cur_node.left: if data > cur_node.left.data: self._is_bstSatisfied(cur_node.left,cur_node.left.data) else: return False if cur_node.right: if data < cur_node.right.data: self._is_bstSatisfied(cur_node.right,cur_node.right.data) else: return False

[@LucidProgramming]

No. I get False for 2,1,2. I think you might want to check your code against my code in GitHub (which is what I just used to check).

[@arjunreddy3615]

@@LucidProgramming But the code used in github is a way different from the one in the video...

[@elachichai]

Thanks for the great video! if is_satisfied is None: # None maps to True -> this is a bit confusing return True might it not be better with if is_satisfied is False: # False maps to False return False return True

[@LucidProgramming]

Thanks for the kind words! Hmm, I'm not really sure that suggestion makes it any clearer. If it's clearer for you though, that works!

[@elachichai]

@@LucidProgramming what would really be nice is a few graph algorithms and dynamic programming. Perhaps design patterns?

[@LucidProgramming]

@@elachichai I don't have much time these days. If you have specific areas of focus, I do offer tutoring and consulting if you'd like to set something up. Cheers!

[@charlesliu7529]

if anyone's wondering how to modify the '_is_bst_satisfied' function to work properly, use: def _is_bst_satisfied(self, node, data): if node.right: if data < node.right.data: if self._is_ordered(node.right, node.right.data) is False: return False else: return False if node.left: if data > node.left.data: if self._is_ordered(node.left, node.left.data) is False: return False else: return False

[@torstenwerneke5261]

Hi Charles ... try this: Good luck ------------------------------------------------------------------------------------ def is_bst_satisfied(self, start=None): return self._is_bst(start if start else self.root , None, True)[1] def _is_bst_satisfied(self, node, val, res): """ inorder """ if node and res: val, res = self._is_bst(node.left, val, res) val, res = node.value, (val < node.value) if val else res val, res = self._is_bst(node.right, val, res) return val, res

[@harshalpatel555]

sorry lucid programmer but your output is wrong and please check and give proper solution

[@LucidProgramming]

How is it wrong? You've given me absolutely nothing to go on here.

[@harshalpatel555]

@lucid programmer your program is working up to only 2nd level nor beyond that.and when i click on your solution link, i found totally different program in it.i do respect ur hardwork..so please help me to sort this mess

[@LucidProgramming]

@@harshalpatel555 Not sure what you're talking about. The link goes to the correct problem.