Binary Search Trees in Python: Checking the BST Property

August 2, 2018 comments 110 Reads

In this video, we will continue our coverage of the binary search tree data structure. Specifically, we will be solving the problem of determining whether or not a given tree we are given as input abides by the so-called binary search tree (BST) property.
The BST property states that every node on the right subtree has to be larger than the current node and every node on the left subtree has to be smaller than the current node. In this video we go over the BST property in more detail on a set of slides to ensure the concept is clear. Once we do so, we will progress to the terminal and write a function that determines whether a given tree satisfies the BST property.
If you are unfamiliar with tree-like data structures, I would encourage you to watch first the series on binary trees. A binary search tree is a type of binary tree. It is important to understand the various terminology used in the context of a tree data structure (root, node, leaves, parent, child, etc.). If any of those terms are unfamiliar to you, or you would like to brush up on them, the binary tree playlist may be found here:
http://bit.ly/lp_bt
This video is part of a playlist on binary search trees:
http://bit.ly/lp_bst
The software written in this video is available at:
https://github.com/vprusso/youtube_tutorials/blob/master/data_structures/trees/binary_search_trees/bst_property_check.py
Do you like the development environment I’m using in this video? It’s a customized version of vim that’s enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:
http://bit.ly/lp_vim
If you’ve found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:
http://bit.ly/lp_subscribe