Trees Solution

[00:00:00]
>> That was a tough problem. I know when I first ran across it, that's challenging. So let's walk through the solution now. And the solution, it'll give you a hint in the name. We'll call it reverse path, because that's what we're ultimately trying to do. And we know we're gonna get some sort of element and we're gonna get the tree.

[00:00:20]
If you're gonna pass someone a tree, it's generally represented as the root. Cuz once you have the root, you can iterate through the entire tree. For many JavaScript developers, it's difficult to conceptualize this because you're used to data structures where, I pass you the data structure, it's the entire data structure.

[00:00:35]
Like an array, or an object, or a set. Whereas a tree is generally only give you the root, and that's known as passing you the tree. So what we wanna do is, knowing this, we wanna walk back up to the root. And along the way, we wanna have a way of recording the path.

[00:00:52]
So that when we jump over to this tree, we walk back down that exact same path. I guess you could think of it like reversing a string. Very similar to the first problem we did, actually, it's not similar at all. But conceptually, you can iterate over backwards, and that's what we're doing.

[00:01:06]
We're iterating backwards over the path that we get. So to start off with, what do I know? I know that I'm gonna need a way of storing that path. And because we know that elements have two parts, they have parent, and the parent, Is gonna have children. But that doesn't really help us, that knowledge.

[00:01:35]
But how do we find the index, or the position of the child that we're currently on? I think I said it already.
>> indexOf.
>> indexOf, yeah, so if we wanted to get, So we can say indexOf some elements. And this would be one part of the path.

[00:01:58]
So if we know the position of the child, so it's gonna be 0 or 1 in this case, cuz they're pretty simple, or 2 or 3, it doesn't matte. We can say 0, this will be, well, there's only one, so this will be 0, this will be 0.

[00:02:10]
And there's no path here cuz we're at the root. And if we replay that, we say parent.children, and we replay that path, so we pop that off, so we say 0, 0, 1. And that would get us the element no matter where it is in the tree. So conceptually, if we understand that, we can understand how to create a reverse path.

[00:02:34]
So the firs thing I wanna do is, I even said it, since we wanna pop off something, I'm gonna say the path is an array. I'm gonna store it as an array of numbers. And I wanna stop when I get to the root, so I'm gonna say while, And I'm gonna say element.parent, actually, I'm gonna say current.

[00:02:55]
Should I say pointer, I'll say pointer, cuz it technically is a pointer, so that's good. We know this while loop will run until we get to the root, because the root will not have a parent. So the first thing I wanna do is, I wanna initialize the pointer, because we're just pointing at different nodes on the tree.

[00:03:14]
So I wanna say, let pointer, and we'll say it's the elements. We wanna start somewhere, that's our base case. So what did we do before? We wanted to get the position of the pointer. So the position is represented as 0, 1, or 2, or 3, or 4, or 5, wherever it is in that array.

[00:03:35]
So we can print that back out. So I'm gonna say index is, we have the pointer. And we're gonna grab the parent, and then we're gonna grab the children. And then we're gonna say, it's not technically an array. It's an array-like structure, but I'm not gonna convert it to an array.

[00:03:56]
Normally you'd have to do something like this, and then you call indexOf. But I'm not gonna do that for simplicity. Again, a whiteboard solution, I care that you kind of have it conceptually down. And then we're gonna say the index of the pointer itself. So this will get us the position in the array that we need.

[00:04:19]
So this will get us the first step in our path. And so I'm gonna say path.push, the index itself. And then I'm going to move the pointer up to the parent at this point. Cuz I wanna know where the parent is in its parent's children array. So I'm gonna say pointer = pointer.parent.

[00:04:43]
Of the whole thing, I think conceptually this is the most difficult part. The fact that you have to go up to look down to see where you are is tricky with a tree, and it's kind of the key to this whole thing. So given this while loop, we can push the path every single time.

[00:04:59]
So looking at this one, this is in position 0, this is in position 0, position 0, position 0, this happens that they're all 0s. So in this while loop, we're gonna end up with a path that's 1 or 0 or 2 or 3, some array. So what do we do now?

[00:05:17]
Since we have the reverse path, we wanna replay that into the next tree. So I'm gonna say the pointer is now the root. So I've now switched to this tree now. And I'm gonna say, while the path has any arguments in it, I'm gonna keep iterating down the tree.

[00:05:39]
Whoops, I cannot spell today. So how do we move down the tree? Yeah, pop, we wanna move that pointer to the next child. So I can say pointer is, we wanna get to the children cuz we're maneuvering down the array. And I'm gonna say, path.pop. That's it, that's a reverse algorithm.

[00:06:19]
When you think about it conceptually, if I just said, give me a reverse path algorithm, that's not helpful as an interviewer. But if I can explain what we're trying to do and I draw it out, hopefully, understanding HTML and DOM structure, you say, there's parents and there`s children, and here's how children would be represented.

[00:06:35]
You can conceptually work this out. And if you didn't get this right, it's okay, this is challenging. But hopefully, it helps grow your understanding of trees, and how to move up and down them. All right, maybe I didn't warn you, maybe I should have warned you that, as we move to the end, it's gonna get more and more difficult, that's just how it is.

[00:06:56]
I wanna give you a warm up question, reverse string one, just to get you going. I could've started with this, you'd be like, [LAUGH] this is a stupid course. I can't believe I took this course, what is he teaching? But as we work our way to here, hopefully it's a little conceptually clearer.