Binary Search Tree (BST): Validator Function

Подписаться 13 тыс.

Просмотров 8 тыс.

50% 1

Code below... In this third part in our series of videos covering the Binary Search Tree data structure, we will take a look at an external function we can implement and make use of to validate our Binary Trees are, in fact, Binary Search Trees (validate that they follow the rules of a Binary Search Tree).
(PYTHON 2)
► Code for this lesson: github.com/bfaure/Python_Data...
(PYTHON 3)
► Code for this lesson: github.com/bfaure/Python3_Dat...
► Original BST Video: • Python Data Structures...
► BST Deletion Function: • Binary Search Tree (BS...
****
► Video series covering various common algorithms in Python:
• Python Algorithms
► Video series covering GUI development in Python (WIP): • Python GUI Development...
End song is "That Kid in Fourth Grade Who Really Liked The Denver Broncos" by Chris Zabriskie"
References:
[1]: stackoverflow.com/questions/4...
[2]: stackoverflow.com/questions/7...

Опубликовано:

5 ноя 2017

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 23

@brianwahome5789 6 лет назад

I also got to apply this in a recent interview. I used an inorder traversal with no repeats and increasing order as my checks. All logic from the print function you taught me. It worked like a charm. Your work is simply amazing man.

@BrianFaure1 6 лет назад

Glad to hear it Brian! Thanks for the support!

@brianwahome5789 6 лет назад

You heeded my request!! Thank you sir!!!!!!

@roblevintennis 4 года назад

You really did a great job with this video from both your explanations to the overall clarity and production. Thanks for putting forth this effort-really helpful Brian! It should probably also be mentioned that this can be solved iteratively if you use a Queue and basically keep a pointer to the previous value as you do an inorder traversal, since in a valid BST, that should produce a sorted list essentially. If ever you encounter that previous > current you return False. I think the recursive solution you have here and the inorder approach are the common ones for this problem and I've been using algoexpert, the elements of programming interviews in python book amongst other resources, so your solution is definitely a perfect recursive solution...nice to see accurate instruction sir! Thanks again :)

@siddhantbhardwaj4268 3 года назад

Excellent video, understood it very clearly !! Thank You !!

@_sls7535 4 года назад

if you want to avoid importing sys you could use float('-inf') as minimum and float('inf') as maximum

@mohamedatef8483 6 лет назад

can you please keep going with this series i wanna understand stacks queues and another algorithms like graph , trees and dynamic programming and thanks for your effort thanks a lot

@BrianFaure1 6 лет назад

Hi Mohamed, thanks for the kind words! I'm actually working on a video for AVL trees right now, and I just got a new mic so the audio quality should be much better. I'll throw your suggestions on the list too, I think stacks and queues would be really interesting topics to cover.

@tolulopeadetula4777 6 лет назад

And Graphs also. Your explanations are simple and easy to understand

@looneytoons2006 5 лет назад

thnx !!!

@parikothari5654 3 года назад

This very useful :) would you also do traversal methods and if binary tree is full or not?

@shantanusharma5617 6 лет назад

Really awesome videos Brian. Can you also do something on AVL(balanced BST) trees? Thanks, keep these videos coming. :D

@BrianFaure1 6 лет назад

sure thing! thanks for watching

@subhamoypaul7029 5 лет назад

please do a video on Heap data structure!

@longhornfinch 6 лет назад

I have a question, Python 3 does not allow sys.maxint anymore. I am not sure if sys.maxsize will have same impact as this one. Does hard setting it to a 64bit Int works?

@BrianFaure1 6 лет назад

If you'd like an easy swap 'sys.maxsize' should provide the same value as 'maxint' on the same system with similar installations, though you should also be able to hard code it. You basically just want a value that's larger than (and smaller than when negative) any value you could possibly see in the tree. The problem with any implementation in Python is that when you go above the value spit back by 'sys.maxint' your int will seamlessly be transformed into a long so it's value can be essentially limitless given plenty of memory. Meaning we can't really put bounds on elements we might see in the tree unless we add in a check to ensure they are of the integer type.

@vijaygr427 6 лет назад

Thank you so much ,Nice video. But if i use this function with our previous binarysearchtree ,i am getting error like if( root.value >min and 6 root.value < max and 7 validate(root.left,min,root.value)and AttributeError: 'BST' object has no attribute 'value' because here i this function its geting root value from Node class .but in our BST implementation we are creating object for BST class ,so BST object has no access to Node class value . Help me to fix this plz

@BrianFaure1 6 лет назад

Hi Vijay! To use this function with our prior BST class you need to pass the root of the BST as the parameter to the function (so validate_bst(a.root), where 'a' is the name of the BST instance, for example). I should have specifically said this in the video, sorry for the confusion.