Transcript from the "Trees" Lesson
>> Bianca Gandolfo: Moving right along, we're going to talk about trees and searching. Trees are a high, I can never say hierarchical, data structure that is useful. I mean, we use it all the time, right? We have the dom tree, right? We have dom nodes for our frontend people out there.
[00:00:20] Trees are used for parsing your code under the hood. It's used for 3D graphics, used for, my gosh, I don't now, like auto-complete, a lot of game logic, searching for things.
>> Bianca Gandolfo: So trees are super, super useful. We use them all the time. We see them a lot in interviews as well.
[00:00:41] So that's why we're gonna spend some time on it today. We're gonna be talking about binary trees tomorrow, and then we're gonna get into the graphs after that. Cool? All right.
>> Bianca Gandolfo: Here we have a tree. I'm just gonna give you a little vocab, a little tour of our tree.
[00:01:00] Trees in computer science are upside down. We start with the root at the top. And we have levels. So this is a binary tree. It's called a binary tree because each node has two children. Notice I called them children. So we have a child/parent relationship between nodes in this tree.
[00:01:21] So we have here a root node. Our root node is a parent of this left child and this right child. And we have different levels. And that's gonna be important in terms of, when we get to balancing trees. Each node we consider its own tree, and then we also can have subtrees.
[00:01:42] At the end, a node that has no children, call that a leaf.
>> Bianca Gandolfo: So that's our tree growing from the root down, down, down. And we have our leaves on the bottom.
>> Speaker 2: And anything that's not a root or a leaf is just a node?
>> Bianca Gandolfo: Yeah, it's an internal node.
>> Bianca Gandolfo: Those are internal nodes.
>> Speaker 2: They're all nodes.
>> Speaker 3: So where are these numbers coming from?
>> Bianca Gandolfo: Yeah, so each node is going to have some data in it probably, right? And normally, when we have examples of trees, we just have integers to simplify. But your tree could have probably objects with lots of different kinds of data in it, yeah.
[00:02:32] Okay, good question. Awesome. So let's think about this interface. So our constructor. So this is a data structure, so we're gonna use our pseudo classical pattern again here. And in our constructor, some important things are storage. How are we gonna store all of our nodes and represent relationships?
[00:02:56] And the root, which is the beginning of our tree, and how we access most things. So methods, not all obviously, are insert. You wanna be able to insert a node or a key into a tree. You want to search for a key, the key is a value. Returns truth exists, false if it's not.
[00:03:17] Trees are often used for search. We're gonna be talking about different search algorithms starting tomorrow. So min/max will return the minimum or maximum value. And removal. This is a little trickier. If you're gonna be removing things in the middle of the tree, and you have to preserve some sort of order.
>> Bianca Gandolfo: If you don't need to preserve any order, then not too hard. Awesome. So this is our tree interface.