Complete Intro to Computer Science

Breadth First Tree Traversals Practice

Brian Holt

Brian Holt

Snowflake
Complete Intro to Computer Science

Check out a free preview of the full Complete Intro to Computer Science course

The "Breadth First Tree Traversals Practice" Lesson is part of the full, Complete Intro to Computer Science course featured in this preview video. Here's what you'd learn in this lesson:

Brian provides a short exercise to practice building breadth-first tree traversals and then live solves the exercise.

Preview
Close

Transcript from the "Breadth First Tree Traversals Practice" Lesson

[00:00:00]
>> All right, so go into breadth first traversal here, you can see here I have a tree here and what you'll get out at the end is, A through K in the alphabet. Let's see if there's anything I need to tell you about first. Yeah, and actually you can do this iteratively or recursively.

[00:00:29]
They both end up being relatively similar. So I'll leave it up to you if you wanna do it recursively or iteratively. We'll do both of them when we come back so you can see what they look like. Let's do iterative first. I don't know, it depends on what you want to do.

[00:00:52]
We'll do, my notes here have recursive first, we'll do recursive first. So if the queue has no length, this is the base case, right. Then you would just return the array, right. Okay, const node equals queue.shift, right. Because we're gonna pull something off the front. Array.push, node.value. Then you can just gonna say a for array.left, or sorry, not array but node.

[00:01:33]
If node.left, then queue.push, node.left, okay. Same thing but for right, so if node.right queue.push node.right. And then you're just gonna say return breadthFirstTraverse queue and array So this is a recursive approach to this. Let's run the test to make sure I got to unskip this. And make sure that traverse is working okay, traversals breadth first test, there it is, working.

[00:02:27]
All right, so let's do this again but let's do const breadthFirstTraverse2 equals queue, array. And we're gonna say while queue.length, we're gonna say const node equals queue.shift array.push. Node.value. Just do this, right? Add the same thing here. And then at the end you just return the array. So let's just change these so this is two and this is one so we can see if this passes our unit test.

[00:03:28]
It's now like that, traverse, there we go. All right, run our unit test one more time. Lo and behold, traversals breadth first traverse. This also works as well. I kinda like this solution. I think it's gonna be more performance and I also just, not that that's really what I'm concerned about.

[00:03:54]
I think this code is easier to read, because I understand, I don't have to conceptualize what's happening with recursion. I can just say, as long as there's stuff in the queue, keep processing the queue. That makes a lot of sense to me. You can get there with this, right?

[00:04:08]
It's fine, but I do prefer this.

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