Implement Binary Tree Comparison

[00:00:00]
>> So let's open back up our Kata machine. Let's navigate down to compare binary trees. Again, we're doing a recursive search. So what have I told you multiple times? Probably create your own function. But let's see how this one looks. [SOUND] The signature, this one actually matches up with what you'd want to do in recursion.

[00:00:18]
So I'm just gonna keep this. I know I'm breaking from tradition, but this makes sense. So let's look at our signature for a second. I kinda gave away the game a bit here, so just be okay with that. Our signature is a. It can either be a BinaryNode or null.

[00:00:33]
b can either be a BinaryNode or null. So what's our base case? Well, there's actually a few of them. There's actually a few base cases. So what do you think base case number 1 is? How do we know at this point we are either equivalent or not equivalent?

[00:00:54]
The easiest one to think of is if a equals null, and b equals null, right? If they're both null, we are currently equal, right? This is a good place to be. At this point with inter traversal, we are equal and we can say that. We don't have to solve for the entire tree.

[00:01:14]
That's what all of recursion combined is for. But at this one moment in time, we can say, hey, if this is what you gave me, that's correct. And that's really what the base case is. It's solving the simple problem, such that the entire recursion becomes simple. All right, next base case.

[00:01:31]
If a equals null, or b equals null, right? If just one of them is null, we've now hit a point where hey, you are no longer equal because one of you are null and the other one's hexadecimal 45. That's completely incorrect, therefore, return false. Awesome, and there's one more base case.

[00:01:51]
What's the last base case?
>> Just one is true or both are true, no.
>> a.value equals b.value.
>> Bill, that's right. If a.value does not equal b.value, I know you said it differently but you got the same answer, then it's not the same. Value-wise, we are not the same.

[00:02:15]
We are false in that moment of time. So now comes the last part, which is always the trickiest part. Which is, how do we do this for the entire tree now? Well, the easiest way to do that, of course, is we are gonna return compare with a.left and b.left.

[00:02:32]
We don't need to look at what they're. We don't need to check if they're nulls or anything, that's what our base cases are for. And compare a.right, oopsies, with b.right. So long as we only hit the return true, it will keep bubbling back up as true, all the way to that point.

[00:02:52]
Cuz remember, if it's true at this point, and my left subtree and my right subtree are true also, then that part of the tree is true. All right, so let's extend this out just a little bit, right? So I'm gonna do 7 and 9, and let's do 7 and 9, and then let's do one more, that's like say 14.

[00:03:14]
Okay, so we go through here. And value, or yeah, the value is equal. So right now, we're not sure if we are true or false yet. We just know that we are passing all of our base cases and we need it to check the rest. So we're gonna go down to this subtree right here, right?

[00:03:32]
This is just a subtree. Any node is in itself a tree. If you think about it, because it is a point in which has children, and so any point of your tree is just another tree. That's what makes this so useful. So we're right here, we check this subtree.

[00:03:47]
Just by visual inspection, you can see they're both the same by shape and by value. So this entire subtree returns true, returns true, which this thing, ampersand, checks each one of these. By the way, did you see that first tri ampersand draw? Very, very hard to do. So long as these both return true, we should be good to go, right?

[00:04:07]
Right, so we do the same thing on this side. We need to see, is this subtree correct? Which ultimately leads, is this subtree the same as the other one? So when we look at this, we are going to return false and true if we were to execute them both.

[00:04:22]
And if we try to ampersand this thing, man, we can't ampersand it, right? We cannot logically add those two, what is it? Boolean, yeah, logically combine those two together. It becomes false. So therefore, this is false, though this is true. And again, we apply the same recursive technique.

[00:04:41]
Are those two together? We multiply true with false, it becomes false. It's not good, therefore, the whole thing is false because one subtree is false within it. So that's kind of working back up logic of just combining those trues and falses. And you can see that right here.

[00:04:57]
So each spot combine our left subtree with our right subtree. Long as they're both true, we're true also. And that makes sense because that means, this case was hit all the way to the end, and that makes sense. That's the only base case that can ever be hit is we just have to keep on hitting nulls, and that's it.

[00:05:17]
Cuz the moment we hit something like this, that whole subtree becomes invalid. Does that make sense? Which eventually makes the entire tree invalid. Beautiful, awesome. All right, is there any questions now that I've potentially shoddily explained it? I tried the hardest I can, very hard, to kinda draw out recursion.

[00:05:38]
It's a topic that's best left to the imagination, Or a really large whiteboard. I think a really large whiteboard could have done it. And you're probably saying, well, you have a really large editor technically. I could have shifted around, but it's just hard, it's just hard. All right, why do we have both of these if statements?

[00:05:59]
Why do we first check to see if they're both null and then check to see if one of them is null? So the first check is to check, have we made it to a point in both subtrees in which we both cannot recurse any further? That's that first check, are we both going to a null node together?

[00:06:16]
That means structurally, we are the exact same, cuz we both arrived to a null together. What this one says is that we're structurally not the same. Because if one of us is null and the other one is a node, we have traversed to the same point and have different structure.

[00:06:34]
Hopefully that makes sense? In JavaScript, yes, we could have used the question mark operator just to see if the two values are equal. We would have been able to condense this step. But I wanted to make it really obvious that this is a structural check, right? This is a structural check.

[00:06:53]
This is a value check, right? I wanted to kind of break those out explicitly because they are truly different. And yes, as I said before, for those that don't understand what I was trying to say, if we just simply deleted that out, that check technically works out for both value and structural checking at the exact same time.

[00:07:17]
Awesome, you guys are great. Great, great question. I think that may have made a better explanation. Okay, let's keep on going. I'm excited, you're excited, we're all excited. So now we're gonna go to a specific version of a binary tree called a binary search tree. It's just classic, it's just absolutely classic.

[00:07:39]
One of the books I recommended yesterday, which I'll bring those up for a quick second. Go right to here. I'm using a mouse, please don't laugh at me. Don't laugh at me. This one right here, the second one. This one just jumps right into binary search trees. I don't believe it even pitstops on trees really at all.

[00:07:56]
But you can check that one out. It has a great explanation of a binary search tree. Also, plenty of good YouTube content on this as well. I just wanted to throw that out there.