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 "Pseudocoding a Binary Search Tree" Lesson

[00:00:00]

>> Bianca Gandolfo: So we're gonna get started with our Binary Search Tree. We're gonna start with some pseudocode, we'll walk through pseudocode, and then we will look at a solution. And then it'll be lunchtime. Sound like a plan? Awesome, and when we come back, we are gonna be talking about exploring.

[00:00:15] We're going to be explorers through our binary search trees. There are different ways to traverse our Binary Search Tree. We'll explore three ways and then we get to the fun stuff. We're gonna learn how to delete nodes from our binary search tree. And that will probably take us to the end of the day.

[00:00:32] And tomorrow, we'll look into balancing cuz at the end we're gonna analyze our operations in the binary search tree, and they seem pretty good. However, in the worst case, we can do better. And that comes into play when we start balancing. But we'll get to that. First let's just start with the constructor.

[00:00:53] So what are some things that we need in the constructor?

>> Speaker 2: You need a left and a right.

>> Bianca Gandolfo: Mm-hm.

>> Speaker 2: And the value.

>> Bianca Gandolfo: So we need a value, we need a left. We need a right. Anything else?

>> Bianca Gandolfo: Nope, nothing else. So we have the value, we have the left and the right.

[00:01:26] If this was a linked list, we would just have a next if this was a n-ary tree we would have an array, right, cuz then it can have multiple. If we were to have three branches per node, we might have a middle. So that's just some different interfaces that you might make in your constructor.

[00:01:50] So insert. So insert, what does it take?

>> Speaker 2: The value.

>> Bianca Gandolfo: It takes the value. And what is the goal here? What do we want to do with our insert?

>> Speaker 2: We wanna find where it goes.

>> Bianca Gandolfo: Yeah, find its proper place. So what are the rules for that?

[00:02:18]

>> Speaker 2: If it's less than the current value, then you need to move add it to the left.

>> Bianca Gandolfo: Mm-hm.

>> Bianca Gandolfo: Okay, what else? What are some other roles? So if the value is less we go left.

>> Speaker 2: [CROSSTALK] Or we can insert it there.

>> Bianca Gandolfo: What's that?

>> Speaker 2: If there's a null at the left we can insert it there.

[00:02:52]

>> Bianca Gandolfo: Mm-hm, go left.

>> Bianca Gandolfo: If there's a left, right? So if there's a left go left. Otherwise, right, else insert, right?

>> Speaker 2: How about equal?

>> Bianca Gandolfo: Hm?

>> Speaker 2: How about it to be equal?

>> [INAUDIBLE]

>> Bianca Gandolfo: What if it's equal?

>> Speaker 2: Yeah.

>> Bianca Gandolfo: Usually in a BST you don't wanna have equals in it, but if it was equals then you could just choose if it would go on the left or the right.

[00:03:26] But normally, you don't wanna have duplicates because it gets kinda tricky when you start deleting nodes.

>> Bianca Gandolfo: So what's the other case? So we have if it's less than.

>> Speaker 2: So less than or equal left, and then if it's greater go right.

>> Bianca Gandolfo: Cool, so if the value is greater than current.

[00:04:00]

>> Bianca Gandolfo: Go right.

>> Speaker 2: It would be the same, if right go right, else if left.

>> Bianca Gandolfo: Mm-hm.

>> Bianca Gandolfo: Else insert.

>> Bianca Gandolfo: What do we think?

>> Speaker 2: That looks like it would work.

>> Bianca Gandolfo: Cool, should we try it now?

>> Bianca Gandolfo: Question?

>> Speaker 2: It should go back to the loop, right, if one.

[00:04:50] Then you go to the second, and then should come back if it's not the end.

>> Bianca Gandolfo: Should it come back?

>> Speaker 2: To the beginning of the comparison.

>> Bianca Gandolfo: To the beginning?

>> Speaker 2: Of the omparison loop.

>> Bianca Gandolfo: So, that would be true if you were going to be comparing it to every single node, right?

[00:05:15] Mm-hm.

>> Speaker 2: Yeah.

>> Bianca Gandolfo: But for this one, you just want to compare it along that one path.

>> Speaker 2: One path.

>> Bianca Gandolfo: Yeah.

>> Speaker 2: But at each node you need to do both, whether it's greater or less, right? Mm-hm, mm-hm.

>> Bianca Gandolfo: Are we missing anything else?

>> Speaker 3: And in practice should we allow duplicates, or should we throw an error if value equals this value?

[00:05:46]

>> Speaker 2: It depends.

>> Bianca Gandolfo: It depends on what you need to do, yeah.

>> Speaker 2: On the GitHub it said you just need to do one. All values in the left subchain of a node are less than or equal to the value of the node.

>> Bianca Gandolfo: Yeah, that's fine, but they also don't have a deletion piece, which we're adding.

[00:06:05] So that's when it gets complicated. So if you're not deleting it, so if you have a binary search tree, and you're just adding all day, and you're not deleting anything or balancing or rotating, you can have duplicates. It doesn't really matter. But once you start rearranging the trees, it gets a little hairy.

[00:06:18] And so, if you're making a binary search tree where you wanna handle deletions and rotations, you wanna be strict about your duplicates.

>> Speaker 2: What are rotations?

>> Bianca Gandolfo: Rotation happens when you basically you're gonna be rearranging your tree so that its height is not super deep. Cuz in the worse case, if your binary tree everything is less, less, less it can look like a linked list, right?

[00:06:44] And so we'll talk about that more in depth but you'll wanna rotate it to find balance. Yeah. And a balance is basically the depth of a tree is never more than one level deeper than the rest. Hope that make sense. So here I can show you, we'll talk about a little bit more, so here we have these different levels so this is balanced, right?

[00:07:14] Cuz it's all the same level, but say we had like three, two, zero, negative one, negative two, all the way to left, then it would suddenly be unbalanced. Because negative two down here would be three levels deeper than the last level. And so when we are traversing this and finding it, it's actually gonna be greater than logarithmic time.

[00:07:40] Because it's not being cut in half every time any more. It's now suddenly just linear, it's a linked list at that point. So in the worst case, it can be the same as a linked list, unless it's balanced. Once it's balanced, which is what we want, and which we'll do probably tomorrow, it preserves our desired time complexity, which is log in.