Complete Intro to Computer Science

# Tries Exercise

## Brian Holt

SQLite Cloud

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

The "Tries Exercise" 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:

Students are instructed to construct a trie for the provided cities that returns the correct autocomplete suggestions.

Preview
Close

### Transcript from the "Tries Exercise" Lesson

[00:00:00]
>> The exercise is under trees. Inside of trees is cities dot j s and in here I have I think 926 of the largest cities in the US. So, your particular task right now, is going to be to construct a tree. Out of all of these various different cities in the United States.

[00:00:29]
I don't think there's any duplicants. In here, right? But you're gonna have a note for our a note for m a note for E, and each one of those is going to have various different notes off of it. So what you're gonna do, down here, as you can see in the unit test You're gonna call something that's called create tree.

[00:00:55]
Once you have a function up here, that's gonna create a data structure with all these various different nodes in it. It's gonna give you a list. So for the first one I only give you 10 cities for the second one, I give you 10 cities for the third one, give me 25 last one 200 200 and then eventually I start giving you 500 and then all of them, right?

[00:01:21]
And then under that, I'm gonna ask you to give me a function on that tree that you give me back called complete and I'm gonna give you a string here. So let's take a look at cities again. If I go up to the first 10 cities, which will be all of these ones right here, there's San Diego, San Antonio and in San Jose, right so these three cities will be in there.

[00:01:52]
So in that test here, if I start asking you to complete san you should give me back San Antonio, San Diego and San Jose doesn't matter what order It's up to you, but that's the job to do here. I think that should be pretty good explanation here. Any questions about the exercise or how to do it, you're just gonna be building a big tree of all these.

[00:02:29]
Do keep in mind that like, again, going back to our picture here, there's an O here and there's an O here. So you'll have hundreds of O nodes, right, and they'll just be in different places. So don't try and we use the same O node for everything, right?

[00:02:44]
You're not gonna have just 26 nodes. For this particular data structure, you're gonna have thousands of nodes. Yeah, and then someone asks for you to complete Bo, what you're going to do is going to say all right, go to the root node hop to be hopped. Right, and then ask what are all the auto completions that I can get out of this this and you'll just say, okay, well I'm gonna go down this path I'm gonna get Boston.

[00:03:14]
I'm gonna go down this path and get Boise and then I'm gonna return those as my answer right. So this is more depth first traversal, right? We're depth first traversing these trees.

### Learn Straight from the Experts Who Shape the Modern Web

• In-depth Courses