Tree and Graph Data Structures Binary Search Trees
Transcript from the "Binary Search Trees" Lesson
>> Bianca: Binary search trees, they are pretty exciting, they are a hot topic in the interview questions circuit. A binary search tree is just a binary tree, we were working with binary trees before the decision tree with yes and no, except that the sub-tree has to be less than the node.
[00:00:23] So here's 19, everything in the sub-tree is gonna be less, and everything in the right sub-tree is gonna be greater than. And that's gonna be true recursively through the tree because that's sort of the nature of these trees. So everything to the left of 11 is gonna be smaller, everything to the right of 11 is gonna be larger.
[00:00:44] I always think like left lower and then right gr, with an R, capital, greater to help me remember which one's less and which one's more.
>> Speaker 2: And this is only, you would use this if your indexes then or something like that? Or you're-
>> Bianca: You will use-
>> Speaker 2: Storing something relationships move the indexes?
>> Bianca: Basically, this is a way to search quickly.
>> Speaker 2: Okay
>> Bianca: It has dynamic, so you can add and remove nodes versus an array adding something into sort of an array can be slow, right?
>> Bianca: Cool.
>> Speaker 2: So they're created, when are they created then, like when would they be created?
[00:01:30] After you've done like let's say to organize some data to make it easily searchable. Is why you would do while you have it like this or what?
>> Bianca: Yeah, yeah, so usually out of the box, it doesn't come as a binary search tree so would need to decide if that's an optimization that need and it's nice if you need to add more data later you can really easily.
[00:01:58] So you have a list of numbers and you need to see if this integer exists in that list super quickly, and also have it be dynamic as well, when you wanna insert and delete, cool. So here we have a binary search tree. Here is the code for it right, we have a root and each node has a value, a left and a right, cool.
[00:02:39] So that's just the binary tree except that we have to follow some rules, right? So the left has to be lower and the right has to be greater.