Python Data Structures #5: Binary Search Tree (BST)

Code below... In this video we'll begin by discussing the basics of the Binary Search Tree data structure, and towards the end, we'll move over to a coding editor and implement the ideas in Python code. Planning an extra video covering the different traversal methods you can choose from when using a BST, possibly another focused solely on the BST deletion function as well.

(PYTHON 2)

(PYTHON 3)

****

► Video series covering various common algorithms in Python:

In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store "items" (such as numbers, names etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by name).
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.

[chloeliu]

After searching thousand of videos at ytb, this tutorial is the most helpful and insightful! thanks!

[BinaryAdventure]

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.

[nackyding]

Best walk through implementation of BST on YouTube by far! Thank you so much.

[nancycarlson]

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.

[robel]

The sound at 7:39 super motivating... and the energy level from 7:25-7:40 is just threw threw the roof.

[Abhi-qiwm]

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 data<curr_node.data:
curr_node.left=self._insert(data, curr_node.left)
elif data>curr_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 :)

[jennaalden]

awesome video! in the function ` fill_tree`, you don't need to return tree, it does it "inplace"

[chaoticpringle]

Thanks for this! I was having trouble understanding my professor when we learned this today.

[HarveyXE]

Thank you for being clear about the values on the left and right side of the tree. Very helpful detail.

[davidarthurpaul]

Fantastic video and great explanations. Rarely comment but please keep this up

[Samuel-lmwb]

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

[fredesch]

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.

[MCNeko]

Thank you, helped me finish my homework without losing my mind x'D

[carlavirhuez]

Finally! I undertand BST! Thanks a lot for yoru help

[vishesh_soni]

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.

[autismo]

very good explanation of binary search trees. straight to the point. explained each of the parts very well. thanks a lot!

[alexsugarman]

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

[RaniLink]

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),

[darkseeven]

32 minutes of yt video (this) = Better_than(My_asd_classes) + Understanding

[zakiahmedqureshi]

easy to understand and pretty well summed up the BST. thanks :)