Search Practice

[00:00:00]
>> So,we are gonna do a practice problem. Is everyone ready for a sweet, delicious practice prompt? So, I did get this in an interview and I have even asked this question, probably 40 times in an interview before looking back on it. This was about 10 years ago I was asking this question.

[00:00:15]
I don't know if I would ask this question anymore. You know, that it's not as I don't think it's that I don't think it's a very great question. But, it shouldn't be a simple question. It really shows if someone is familiar with data structures or not, cuz the question itself isn't hard.

[00:00:27]
So, the question, of course, is comparing two binary trees to see if they're both equal in shape and in structure. So, let me show you what I mean. So, let's do this. So, let's just pretend we had five, Three, hexadecimal of 45. There we go, all numbers fantastic and we had another tree that was five.

[00:00:54]
Three, again hexadecimal of 45 just a fun number right we're just putting in fun numbers right now. So, we have two trees we can visually see they're both same in value and same in shape correct Yes, yes absolutely. So, let's try breadth first search first on this thing.

[00:01:10]
So, breadth first search, of course is a tree level walking. So, we had visit 5 first, is 5 equal to 5? Say, yes.
>> Yes.
>> Yes, thank you. All right, then we'd go we'd add each one the children, add left then add right. Therefore, we visit 3 necks is 3 to 3?

[00:01:27]
>> Depends on what you're doing definition of is.
>> My goodness, yes, 3 is equal to it it's awesome, okay? Is the hexadecimal 45 equal to the hex The decimal 45. Yes, my goodness, this looks like we have found a solution, right? We feel like we found a way we could traverse these two trees and actually see if they are equal, correct?

[00:01:48]
All right, well always try to prove yourself wrong in an interview so let me draw one other way.
>> Five, three, hexa decimal of 45 tree level search again, let's go first. We would start here is five equal to five. Yes, it is. We'd go here. We'd add left and right we'd add left and right, we'd go to three, Is three equal to this.

[00:02:13]
Yes Now we add left and right add left and right. we would go here on this one we'd go here on this one. Is 45 or hexadecimal 45 We go to hexadecimal for five absolutely it surely is. But, are we structurally equivalent. Now, we've screwed that up obviously our algorithm sucks, we failed the interview we no longer have a job at the widget factory what are we going to do.

[00:02:39]
Well, that's because we didn't use the right traversaling. Remember what I said about depth first. Depth first preserves the shape of the traversal. So, if we were to do this again but go depth first, we would start at 5, and we'd say, hey, are you equal to 5?

[00:02:58]
You are. Let's both go down the left-hand side of our tree together. We'd go down to 3, it would go down to 3. We go down to 3, it would go down 3, there we go. 3 on 3. Okay, hey, you're equal, let's both go down our left-hand side.

[00:03:13]
I'm null, are you null? You are awesome. Come back up to three. Let's go down our right hand side. You're not, I'm not fantastic. Come up to three. Go back up to five. Let's go down our right hand side. You're hexadecimal 45,
>> [LAUGH]
>> Everything is fantastic.

[00:03:27]
Again. No, no walk back up. Everything's great. We found a solution that works with this case, but does it work with this case? Well, let's find out again. I always walk through solutions it does make interviewers happy, hey I'm at five euro five fantastic, high five in fact.

[00:03:43]
So, the high five, they're equal, let's go down the left hand side together. This is three, I'm at three, awesome, another good job here, let's go down the left hand side together. Hey I'm not, what are you? I'm hexadecimal 45. Man, we're no longer compatible, the whole thing blows up It's bad.

[00:04:03]
Right? So, depth, first search does preserve shape, whereas breath first search does not. And I think that is an extremely important kind of distinction to make, just because it'll help you really understand the values or the merits of recursion versus breath,first search. All right.