Transcript from the "In-Order Traversal" Lesson
>> Bianca Gandolfo: Binary search tree. So we implemented it, we did some exercises, now we're gonna talk about exploring them. So we did a little bit of exploration, right? When I think about exploration in an algorithm, I think about basically touching every single node in a tree looking at every item in an array.
[00:00:28] Going all the way from head to tail on the link list and traversing through. So that, you could maybe do some transformations with your data. That would be the main thing. Or,
>> Bianca Gandolfo: I don't know, maybe you wanna add up all of the numbers in your binary search tree for some reason?
[00:00:49] Whatever it is, you want to look at every node in your binary search tree, we would be doing these traversals. So there's three different ones. And the order is important, mostly because binary search trees are ordered. And the order for whatever your implementation is, is probably gonna matter.
[00:01:10] And so that's why we have these three orders. So let's just look at our picture really quick. So let's imagine that we're looping through, and we want to make this the most excited binary search tree in the world. And this is my favorite data transformation. It's really good for Twitter plugins when your Twitter feed is just full of boring people, and you want to loop, and you just want to concatenate some explanation points at the end, to give some excitement to your life.
[00:01:45] So that would be an excitement transformation. We just put usually three. I think three is good. Maybe two. One if you're kind of subdued at the end of each data, right? So, in the case that it's your Twitter feed, the data would be the text nodes in your twitter feed, and in this case we have these numbers and we'll just transform it into exciting numbers with exclamation points.
[00:02:11] So to make that happen we need to visit all of our friends here in our tree, and that's what we're gonna do. What do you think the time complexity of that kind of operation is? I mean, it's super useful, and it's something you need to do every day.
[00:02:25] So it's good to know what the time complexity of that kind of operation, every time you wanna make your data structure excited.
>> Speaker 2: Linear?
>> Bianca Gandolfo: Why do we think this is linear?
>> Speaker 2: To do one thing to all of the things?
>> Bianca Gandolfo: Yeah. Yeah, exactly. So it's gonna to be linear because you're visiting every node once.
[00:02:52] Hopefully just once. If you're doing more than once then you're probably doing something extra.
>> Speaker 2: Too much excitement.
>> Bianca Gandolfo: Yeah, too exciting. And so, if our binary search tree doubled, right? It's twice as much work. That's the idea behind a linear algorithm, great.
>> Bianca Gandolfo: So, before we jump in.
[00:03:18] We've done some exploration before, it's not our first rodeo. How have we explored a linked list in the past?
>> Speaker 2: Well, we'd start at the beginning and then we'd go on the next object.
>> Bianca Gandolfo: How do you say that in coding language, though?
>> Speaker 2: We traverse?
>> Bianca Gandolfo: Yeah, you traversed it.
>> Bianca Gandolfo: There was not abracadabra, explore link list!
>> Speaker 2: Loop through?
>> Bianca Gandolfo: Yeah. We use a loop. What kind of loop do we use?
>> Speaker 2: You use the Y loop.
>> Bianca Gandolfo: Mm-hm. For our linked list, if you wanna explore it, we did a little bit when we were just searching through our linked list when we will contains for a linked list yesterday.
[00:04:12] Is it yesterday? Think so, I get my days confused. So we explored it simply by doing a Y loop, we just made sure we didn't have an infinite Y loop by incrementing to the next next, the next this dot next equals this dot next next, something like that.
[00:04:32] Cool, seems pretty straightforward. Right start at this, and you go this dot next, this dot next dot next, this dot next dot next dot next, all the way until you get to this dot next dot next dot next dot next. And then you just can't say it anymore.
[00:04:48] So that's how we explore Linked List. What about an Array? We wanted to look at all elements in the Array, I think we do this almost every day.
>> Speaker 2: It's for a loop.
>> Bianca Gandolfo: Mm-hm. Just for loop, look through it, concatonate all those exclamation points as needed. Cool, object?
>> Speaker 2: For loop?
>> Bianca Gandolfo: For in loop usually.
>> Bianca Gandolfo: What about our stack and queue?
>> Bianca Gandolfo: It's kind of a trick question, you're not supposed to be able to do that.
>> Speaker 2: Right.
>> Bianca Gandolfo: [LAUGH]
>> Speaker 3: I was gonna say do we do that?
>> Bianca Gandolfo: No.
>> Speaker 3: You have to [INAUDIBLE]
>> Bianca Gandolfo: I mean you could probably do it, right, but you're not really supposed to. The whole point of the stack and queue is you are not supposed to be able to look through it in the very generic implementation. But, create it as you will as you need for your life.
[00:05:50] And you'll be like, I really need a stack or a queue, where I can look at everything. Except Bianca said that I shouldn't do that-
>> Speaker 3: [LAUGH]
>> Bianca Gandolfo: So now, now what do I do? Cool, awesome. So we are explorers, we have Indiana Jones hats and stuff like that, we know how to get down.
[00:06:11] Now we're going to talk about how we might do this with a tree. A binary tree, specifically. So, the first one is called an in-order traversal. Why do you think it might be called an in-order traversal?
>> Speaker 2: Equalling in order.
>> Bianca Gandolfo: Yeah, so it goes in order. But what's the order exactly?
>> Speaker 2: From smallest to biggest.
>> Bianca Gandolfo: Yeah, so you're gonna go from smallest to biggest, exactly. So how do we do that? Well in this picture it makes it look easy.
>> Speaker 3: That is so cool.
>> Bianca Gandolfo: You just follow the dotted line obviously, right? You start at 11, you follow the dotted line, you show up at three.
>> Speaker 3: That's so cool.
>> Speaker 2: Find the smallest one first. Yes. So you go left until there's nothing left and then you go right.
>> Bianca Gandolfo: Yep, yep, yep. But you can't. When you get to 11 you have to switch to left again.
>> Speaker 3: Think about if there were more levels to that.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: Well if you're on the left line you go to the- One of the above?
>> Bianca Gandolfo: So just know, what's that?
>> Speaker 2: We call the left?
>> Bianca Gandolfo: Yeah, so we start at the left, exactly. So we have to start at the route null. We don't have a choice.
>> Bianca Gandolfo: I was gonna say thanks, Obama, but I don't know if that's appropriate to be political.
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: [LAUGH]
>> Bianca Gandolfo: I stopped myself and then I went there, whatever. So we start at 11, and then we have two choices, we can go right, or we can go left.
[00:07:50] So which way do you, we have to go left, right? And we're at 7, and then we have to go left, or we can go right. We have to go left. Go left, right? Do we see a pattern here? So you go left and then we're calling a function on each of these data points.
[00:08:04] That's a transformation, right? We're not just like getting and then moving on through life. We wanna actually do some work on each of these nodes. Cool, so we go left left left, then we do some work. There's a callback function, our excited number function that puts exclamation points.
[00:08:27] Then, perhaps, we pop out maybe from a recursive call, maybe, I don't know, and then we want to go right. Sorry, then we wanna do it with the current one, right? So we pop out of that. We want to call it, on our current node, 5, because it's the next one.
[00:08:49] Then we want to go right and call it on our right node, 6. And then maybe we'll pop out somehow back to 7. And then, wait. It's the same thing all over again. Just like the left.
>> Bianca Gandolfo: The right. And then we're going to pop back out to our top root node, okay?
[00:09:17] All right.
>> Bianca Gandolfo: Why is this not showing?
>> Bianca Gandolfo: Okay.
>> Speaker 2: I didn't think the trees had knowledge of their-
>> Bianca Gandolfo: Of their parents. [LAUGH]
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: [LAUGH] They're orphan trees.
>> Speaker 2: You know what I mean? How is 6 getting onto 7?
>> Bianca Gandolfo: Yeah, they don't.
[00:09:43] That's the thing is they don't have, well, I mean it's a loop data structure right, so they're all together in the same world. Did I say loop data structure? I meant nested. Nested data structure. So they all live in the same world, but they don't necessarily have a pointer.
[00:10:01] There's no like, this.parent.value, right? There could be, you could implement that, but we don't do that with our binary search stream. We don't have to,
>> Bianca Gandolfo: And we'll see why.