Tree and Graph Data Structures

Binary Tree contains Walkthrough

Tree and Graph Data Structures

Check out a free preview of the full Tree and Graph Data Structures course

The "Binary Tree contains Walkthrough" Lesson is part of the full, Tree and Graph Data Structures course featured in this preview video. Here's what you'd learn in this lesson:

Bianca walks through each recursive step in the execution of the contains solution for binary trees and discusses usage of recursion in interviews.

Preview
Close

Transcript from the "Binary Tree contains Walkthrough" Lesson

[00:00:00]
>> Bianca Gandolfo: All right, we're gonna do it, we're gonna walk through it again.
>> Bianca Gandolfo: All right, so let's simplify our tree,
>> Bianca Gandolfo: To,
>> Bianca Gandolfo: Look something like this. So we have a and we have b and c,
>> Bianca Gandolfo: And then c contains d.
>> Bianca Gandolfo: Does that make sense? So we have a tree.

[00:00:45]
The root note is A. Then we have B. We have C. And then we have D. Yeah. Okay. So, let's look for
>> Bianca Gandolfo: The value
>> Bianca Gandolfo: Here. So we'll have left and right, well, we'll keep yes, on that one's fine, okay. So the first thing, let's look for D.

[00:01:24]
Actually, let's look for C. So we're gonna pass this value, C. So for our first one, is this .value is what?
>> Speaker 2: A equal to C, that's gonna be false.
>> Bianca Gandolfo: Okay. And then we jump here. That was a little weird, but we can get through this. So this .yes which is gonna be a left.

[00:01:53]
I’ll just call it left.
>> Bianca Gandolfo: Okay. So Stefanie do we have a this .left?
>> Speaker 3: Yes.
>> Bianca Gandolfo: Okay. And because we have a this.left we can move on to the second side. What if this was false, what would happen?
>> Speaker 2: It would check the
>> Bianca Gandolfo: It would just skip this.

[00:02:18]
Yeah. Okay. But it's not false so, we don't skip it. We call this,
>> Bianca Gandolfo: Eli, what happens next?
>> Speaker 2: Well it's gonna do another contains on the b tree, the tree that has b's above it.
>> Bianca Gandolfo: Yeah so we're gonna do another contains. This is gonna say does b equal c?

[00:02:42]
No. Kareem, what's gonna happen next here?
>> Speaker 2: Gonna check to see if there is a right I guess or-
>> Bianca Gandolfo: Well.
>> Speaker 2: It's gonna go to see if there's a left.
>> Bianca Gandolfo: Yeah, exactly, is there a left?
>> Speaker 2: No.
>> Bianca Gandolfo: Okay, Seth, what happens next?
>> Speaker 2: It's gonna check if there's a right.

[00:03:08]
>> Bianca Gandolfo: Yeah, so it skips over this completely, it's gonna check if there's a right, is there a right?
>> Speaker 2: There's not.
>> Bianca Gandolfo: What happens next, Aisha?
>> Speaker 3: It goes back to the beginning.
>> Bianca Gandolfo: Yeah, so we return here. What are we going to return?
>> Speaker 2: False.
>> Bianca Gandolfo: False, okay.

[00:03:34]
So,
>> Bianca Gandolfo: We're done with this, we're gonna pop it up, here. This is now false, right? Do you see how that happened? This returned false.
>> Bianca Gandolfo: Okay? So, false. Okay? Remember we are back at a. All right, so the next thing we're gonna check, who's next? Sony, what's the next thing that happens?

[00:04:18]
>> Speaker 2: You will check on c.
>> Bianca Gandolfo: Yeah, so this.right
>> Bianca Gandolfo: We have it so then we then call it again. Like this.
>> Bianca Gandolfo: All right, so we're at C now. So C equals C.
>> Bianca Gandolfo: Is gonna return true. So we know we're getting down here returns true.
>> Bianca Gandolfo: And so this evaluates to?

[00:04:55]
>> Speaker 2: True.
>> Bianca Gandolfo: And what does this return?
>> Speaker 2: It's true.
>> Speaker 2: So it works?
>> Bianca Gandolfo: Looks like it works.
>> Bianca Gandolfo: Cool, any questions?
>> Speaker 3: Do we need to check the edge case of where we are looking for it now, when it doesn't exist in the tree to make sure that that execution path will still return as we expect?

[00:05:26]
>> Bianca Gandolfo: Yeah, sure. So, I think, the execution path is gonna be the same as this. It would be false or false.
>> Speaker 3: Okay.
>> Bianca Gandolfo: Which is false.
>> Speaker 3: I believe you.
>> Bianca Gandolfo: Yeah, for sure. But, I think, if you're feeling like when you're doing this on your own you're, I'm not sure.

[00:05:42]
Definitely, definitely do it. And like, just explore everything. And the more you do that the more you kinda get a sense for how this works and you can kinda pick up on like, okay, if it works on this size it should work on that side. Which is kinda the magic of working with trees.

[00:05:58]
Especially binary trees, like you do one thing on the right side and one thing on the left side and recursion. It's the same thing, so if it works on one side it's gonna work on the other side generally, but definitely just test it out on your own time so that you can feel confident about it.

[00:06:15]
How we feeling?
>> Speaker 3: Great.
>> Bianca Gandolfo: Great, or middle? Middle meaning great, yeah. It's cool, right? It's very elegant and that's what is nice about recursion. But it's not obvious or intuitive which is a kind of recursion, I think in an interview setting depending on where in your at, like I would say, if you're interviewing at a big company, the expectation is you do recursion, if it's like a very data structure algorithm heavy interview, just do recursion.

[00:06:55]
But if it seems more, like there's some interview places and it tends to be more startups, they kinda want you to hit the ground running, they don't care if you know how to reverse a link list, they wanna know, hey, can you like create this view and render data if you're on the front end or whatever backend people do, I don't know.

[00:07:11]
So then you're more interested in that. And I say if you're more comfortable doing an iterative solution in that setting, prefer that. In a more academic feeling setting you can prefer recursion that’s kinda how I see it though.

Learn Straight from the Experts Who Shape the Modern Web

  • In-depth Courses
  • Industry Leading Experts
  • Learning Paths
  • Live Interactive Workshops
Get Unlimited Access Now