This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.

Transcript from the "Binary Search Tree Overview" Lesson

[00:00:00]

>> Bianca Gandolfo: Binary search tree, quick review, so we have our n-ary tree, which we just created. We have parent/child relationships, each node can have n amount of children. And we have this sequential access, right? Where we start from a root node, and we access the children from there, unless we have a reference, right?

[00:00:19] So a binary tree is the same as the n-ary tree, except that each node can have a maximum of two children, so we have this concept of a left and a right. And then, our next sort of iteration on top of that, is our binary search tree, which is the same as a binary tree, except that all the nodes on the left, it's a search tree and everything is gonna be sorted in this tree.

[00:00:42] Everything in the left, the values are less than the node, and everything on the right, the values are greater. The way I remember left and right is, because like most people that I know are right-handed, so I think like more right, left less. And so, that's how we set up our binary search tree.

[00:01:03] And the entire sub tree in left is gonna be less than the right, and the right is gonna be greater. Cool? Do we have a visual, in our head here?

>> Bianca Gandolfo: Where's our visual? I don't have a visual. That's okay.

>> Bianca Gandolfo: So, the thing about performance. So we often think about searching and lookup when we have some sorted list, right?

[00:01:42] So we have our sorted array, which might be a simpler version then de-sorted nested arrays, right, which are binary search trees. We saw our n-ary tree is just a nested in arrays, right? Objects in arrays, binary search tree is gonna be the same idea. For an array your value look-up by key is super fast.

[00:02:04] However, if you need to insert or delete, it's a little bit slower. And we saw that, right, cuz we would have to shift over all the elements in an array, to make it happen. Yeah? So with the binary search tree,

>> Bianca Gandolfo: These things are usually a bit faster.

[00:02:25] So a value lookup by key inserting and deleting, and that's because our data structure is flexible and we don't have contiguous usage of memory space, like you might with an array, right? So if you wanna add something to the beginning of the array, you just shift everything over to the right.

[00:02:44] Which for a binary search tree, simply inserting means that you're going to traverse the tree, and find its place in the list. Let's find my picture of the binary search tree. Where did it go?

>> Bianca Gandolfo: Where are you, picture? We have it in another slide deck, for sure.

[00:03:09]

>> Bianca Gandolfo: Circular tree.

>> Bianca Gandolfo: Okay, so this is our binary search tree.

>> Bianca Gandolfo: Can you guys see that? It's right there.

>> Bianca Gandolfo: So we see here, we have our root and say, we wanted to add, but just say, we add 7, we're gonna add it to the left cuz it's less than 11, versus 15, which is gonna be right.

[00:03:43] Notice that this entire subtree is going to be greater than 11. This entire subtree is gonna be less than 11, right? I was talking about that earlier. And let's imagine that we wanted to insert the value 2, into this tree. It would start from the root and we would say, is 2 greater than or equal to 11?

[00:04:09] It's less, so we're gonna go left. So greater than or equal to 7 is less, so we're gonna go left. Greater than or equal to 5, it is less, so we're gonna go left.

>> Speaker 2: Wouldn't it be easier to reorganize the structure, so that the 7 becomes the node and 2 show and become 1, greater than that, which is 11, and then the smaller two on the left side.

[00:04:40]

>> Bianca Gandolfo: So yeah, so the greater is still the 7 subtree are greater than the left subtree still. So if its 2, where we want it to go, is to the left of the 3 because it's less than 3, versus, if we were to add 4, it would go left, left, left, but once we get to 3, we were gonna add it then to the right.

[00:05:00] Does that make sense? So, 2 would go here, 4 would go to the right.

>> Bianca Gandolfo: Cool? So what would happen if we wanted to add 19?

>> Bianca Gandolfo: What would be the first thing that happens?

>> Speaker 2: You go to the right of 11.

>> Bianca Gandolfo: Mm-hm. So we'd say, is 19 less than or greater than?

[00:05:29] It's greater than, we're gonna go to the right, then what will happen?

>> Speaker 2: Same thing.

>> Bianca Gandolfo: Less than or greater than? It's greater, so it's gonna go to the right.

>> Speaker 2: Mm-hm.

>> Bianca Gandolfo: 20, less than or greater?

>> Speaker 2: Less.

>> Bianca Gandolfo: Less, 18?

>> Speaker 2: Greater.

>> Bianca Gandolfo: Greater, then it will come out on the right.

[00:05:51]

>> Bianca Gandolfo: And so that is how we have a binary search tree. Cool. And that is another reason why insertion is easy, right? We don't need to rearrange an entire array, we just need to traverse down into the proper place. How much less work is that probably?

>> Speaker 2: Well, it would be a recursive, right?

[00:06:19]

>> Bianca Gandolfo: Mm-hm?

>> Speaker 2: So, versus the loop.

>> Bianca Gandolfo: Yeah, so we wouldn't have to look at all of our elements.

>> Speaker 2: So we'd only be cutting it in half?

>> Bianca Gandolfo: Yeah, so when we cut something in half each time,

>> Speaker 2: That's the login.

>> Bianca Gandolfo: It's what?

>> Speaker 2: Login?

>> Bianca Gandolfo: Yep.

[00:06:34]

>> Speaker 2: Yeah.

>> Bianca Gandolfo: Yep, so logarithmic time.