Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "BST Review" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

Before continuing with her min/max node deletion pseudocode, Bianca does a brief recap of Binary Search Trees.

Get Unlimited Access Now

Transcript from the "BST Review" Lesson

[00:00:00]
>> Bianca Gandolfo: So we're in day four. We're gonna review a little bit about binary source trees only so that we can get to deleting our nodes. Then we're gonna get started with graphs. That's today. Tomorrow we're gonna do some hash tables. It's Saturday, we're gonna decide a little bit later if we're gonna have a half day or a full day tomorrow, just depending on sort of attendance.

[00:00:26] It's been a long six days. So Mark'll be sending out surveys, seeing who's planning on coming. For those of you who are here or in the chat, I just wanna take sort of an informal survey really quick. Who is gonna be here tomorrow? Raise your hand.
>> Bianca Gandolfo: Cool, okay.

[00:00:46] So most of the people. Cool, okay. And we'll definitely be covering hash tables tomorrow.
>> Bianca Gandolfo: Beyond that, we're still sort of TBD.
>> Bianca Gandolfo: Cool, so if you have any strong opinions on what you wanna see, talk to me and I can, be prepared for me to maybe say no, but let me know and we can think about it.

[00:01:14] Cool.
>> Bianca Gandolfo: Awesome.
>> Bianca Gandolfo: Ready to go? Let's do this.
>> Bianca Gandolfo: Let's just start from the beginning for a second.
>> Bianca Gandolfo: So binary search trees.
>> Bianca Gandolfo: What is it?
>> Bianca Gandolfo: What is a binary search tree? Rosie, do you remember? Where you here yesterday?
>> Rosie: I wasn't.
>> Bianca Gandolfo: Okay, how about Jen?

[00:01:51]
>> Jen: Trees with only two children. Maximum of two children each.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: David, do you know some more rules for a binary search tree?
>> David: Well, the rule is that every node in the left subtree has to be less than the current node.
>> Speaker 5: And every node in the right subtree has to be greater than the current node.

[00:02:15]
>> Bianca Gandolfo: Yep, absolutely, cool. So there we are. Some things that we did is we traversed them in different orders, in order, preorder, post order. We inserted, we searched for things, and then we started to talk about deleting nodes. And it seemed fine for a moment, right? We first deleted three, and we're like, cool.

[00:02:43] We just set the parents left to null, right? When we're deleting the minimum. We're like, that's cool. And then, we left off with, okay, so the next run of this method, deleting five, presents a different challenge, right? And so, we left off with, so how do we account for that?

[00:03:10] How do we account for a sub-tree here, being longer, right? We have a balanced tree, but what if it wasn't? Does it matter? Does it change anything? So that's where we left off. And I asked you
>> Bianca Gandolfo: What do we do?
>> Bianca Gandolfo: If you had to guess, Andy, what would you guess we would do, just by looking at this?

[00:03:44]
>> Andy: So instead of to delete, say we were deleting 5.
>> Andy: I mean, it has two child nodes, so it wouldn't really work. But I was thinking if it only had one child node instead of nulling out the parents child, you could set the child to the grandchild?

[00:04:09]
>> Bianca Gandolfo: Yeah, so for the minimum, right? If 5 was the minimum, it would have no left. So there wouldn't be two child.
>> Andy: Okay.
>> Bianca Gandolfo: So it would only have a maximum of one. Otherwise we would, if we're deleting the minimum, right? Otherwise we'd just delete the left.

[00:04:25] So that's part of the requirement here.
>> Andy: Okay, so that would work, then. So instead of just nulling out 7's left, you could set 7's left equal to 6.
>> Bianca Gandolfo: Yep.