Trees Exercise

[00:00:01]
>> Trees. Normally, I would say. I don't know, in an interview, I don't know if I'd ask something about trees unless they're a pretty senior engineer cuz it's not something we think about. This next problem is one that, I failed it. I failed it hard, cuz I never thought about trees.

[00:00:22]
But once I understood how to solve the problem, really it changed my perspective on the way trees work. I'm like, okay, I get it. I get how to iterate through a tree. But until I was forced to do it and forced to fail, I didn't learn anything. I was like, yeah, trees, I know trees.

[00:00:38]
The DOM is a tree, cool. When am I have to use this? But until I got this question and failed it, I didn't force myself to learn it. But once you learn trees, you kind of, the knowledge you learn is applicable to any tree. Cuz trees are, the way you traverse a tree is generally gonna be the same way.

[00:00:55]
There's different types of trees, which I'm definitely not gonna go into. I pretty sure there's another Frontend Master's course which talks more about tree algorithms and different types. We're not gonna do that today. We're just gonna do the most basic tree. But gonna start off with a tree.

[00:01:09]
If you didn't know anything about trees, which I didn't at the time, all trees have two properties. They have a root, where the tree begins, and they have nodes. And to break up those nodes, the child, there's are parents and there are children. The children, of course, are the children of the parent node.

[00:01:29]
So the root, everything underneath the root is the child. But of course the root itself is a node as well. And the way you wanna think about this programmatically is the parent. If you thought, I don't know, parent.children? How would you represent the position of the children on a tree?

[00:01:48]
I know, it's a little tricky, but what if we said this was zero and one? What if I had three children? It'd be zero, one, two. Zero, one, two, three, four. That's how we would jump the order of the tree if you're reading from left to right, and that's generally how you think about it.

[00:02:02]
Programmatically, we'd say, that's an array. So think of this in terms of JavaScript objects. Parent.children is an array of items. So child 1 at index 0 is gonna be some node, it's gonna be this node. Child 2 is gonna be this node, and so on and so forth.

[00:02:21]
This will be applicable for this next question. So what's a tree that we all know and love? I've said it like four times already.
>> DOM.
>> The DOM, yes, it's a tree. And what does the DOM have for properties? You have a root, that's HTML, it's always gonna start with HTML.

[00:02:43]
Then you have maybe a body, a title, a head. It's a tree, so what does every tree have? Give you a hint. Child nodes. And you've probably actually used that, we might have used that in an early example. .children is how to get the child node to the parent.

[00:03:00]
So every HTML element has a children, it has a parent you can guarantee that. If I wanna Iterate through an array. So if I click something and I wanna say, what did I click on? Cuz event's not working or something. I would just say .parent, .parent, .parent, .parent.

[00:03:15]
I'd just iterate up. If I wanna iterate down, I say that children at position zero, dot children opposition one and that way I'm moving through a tree. I will give you fair warning, this one is was challenging. But again, i think it's helpful because once you understand the solution, this problem you understand how to iterate through a tree.

[00:03:34]
Using Dom as a good exposure, that if you understand Dom you understand, i can iterate through a binary search tree or I can iterate through a vl tree. Or many different types of trees. So for this particular problem, I have drawn it out. You're given two DOM trees.

[00:03:52]
So think of, I don't know, two different copies of webpage if you wanted to. Or let's say you offloaded your DOM, your virtual DOM, into a web worker, and you wanna iterate through, you wanna manipulate them both So you can use HTML directly on those. But you know, we're one element isn't a tree.

[00:04:10]
So you have a DOM tree. It's represents things that are just HTML. Let's say you have a clone of that exact same tree. How would you get the path to a given element? So if I give you the location of a button One domTree, how would you get to that button in an identical domTree.

[00:04:28]
So I'll say the more formal way we have two identical boundaries A and B. For DOM tree A, we have location and element creative function to find that same element in DOM tree B. For this one, I will give you 20 minutes and I'll definitely help you out.

[00:04:46]
This one is tricky, but think of what we know already. What do we know about DOM tree a? We know that it has a root, fine. But we're not given the root. We're given an element to find, and we're given the other tree. So how would we get to the root, given an element, any node?

[00:05:07]
So given this node how do we get up to here?
>> Recursion from the parents.
>> Exactly, you can use recursion. I would just say a loop and just walk back over. Because this node we know for a fact has a parent. And then this node has a parent and this node has a parent.

[00:05:29]
So you can walk back up the tree just calling the parent every time. I'll give you another hint in another five minutes or so, but that should start you on the right path. All right. Right, mid problem hint since this one is a Challenging, especially if you never thought about trees.

[00:05:48]
But let's think about the things we know. We know we're probably gonna need some sort of function. And that's gonna take an elements and then it's gonna take that other tree, okay. But ultimately what are we trying to do? And if I say it, you'll be like, We're trying to go up the tree.

[00:06:15]
We have this element and then we have this other tree. That's what we know. We're trying to get to here, essentially. And then, we can replay that same path to get to here. So that would be a reverse path algorithm. So essentially you start here, how would we walk up the tree?

[00:06:36]
We would call dot parent. And then we call the parent and then we call the parent. If there is no parent, we're at the root. So if we can store that. We can then replay that, reversing it to walk back down the tree to here. Remember that every element has a parent and it has children.

[00:06:59]
That's the hint I'll give you. So I'll say, you want to iterate up until you hit the root node. And then you want to jump back, go back down.