Trie Data Structure Implementation (LeetCode)

Рет қаралды 70,500

Күн бұрын

📚 Trie Deep Dive Video - • 5 Data Structures Expl...
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmichael.com
00:00 - Intro
00:19 - Trie Summary
00:44 - Problem Description
01:30 - Example Walk Through
03:55 - Code Walk Through
10:53 - Time and Space Complexity
A trie is a tree data structure where the nodes store letters inside of the alphabet. When these nodes are connected, they form words in which then you can use this structure to search prefixes and full words in an efficient time. For this problem, we must implement a trie data structure by completing the functions insert, search, and startsWith. Our insert function will add a word inside of the trie. The search function will return true or false as to whether a word is inside. Finally, the startsWith function will return true or false if a prefix is inside of the trie.
Since we only have to worry about words containing lowercase letters, we can create an array of nodes of size 26 where each index will be responsible for storing an individual lowercase letter. To implement insertion, we will have node called 'curr' which starts at our root node. We move this 'curr' node down the branches of our tree creating nodes along the way for each character in our word. Our search and startsWith functions will have very similar logic where we move down the branches and return the last character in the word we are looking for.
The time complexity for all 3 functions will be big oh O(M) where M is the number of characters we have in our word. We must traverse M nodes in the worst case when performing these functions. The space complexity of insert will be big oh O(M) because we must create M nodes per insert. Finally, our space complexity of search and startsWith will be big oh O(1) constant time since we do not initialize extra memory in those functions.
----------------------------------------------------
LAKEY INSPIRED - Blue Boi
/ lakeyinspired
/ @lakeyinspired

Пікірлер: 127

@gregoryrobertson Ай бұрын

Man, whenever I see your face after a google search on a data structure I feel a sense of relief. Thanks a lot for making these amazing videos.

@AlgosWithMichael Ай бұрын

That is such a huge compliment, thank you so much!

@chiranjeevipippalla 3 жыл бұрын

This is gold. 👏👏👏 Couldn’t find a better explanation of Trie. Thanks brother

@AlgosWithMichael 3 жыл бұрын

No problem 👍

@shubhammittalSHM 3 жыл бұрын

What an amazing explanation! By far the best. He makes difficult concepts look so easy and very intuitive. Thank you so much, Michael.

@AlgosWithMichael 3 жыл бұрын

You're very welcome!

@lakshmireddy1488 3 жыл бұрын

checking for Trie implementation all over the internet finally found and he also explained very well thanks, bro....

@hellorsanjeev11 3 жыл бұрын

Best video on Tries on KZfaq - Thank you so much. I just subscribed myself.

@mukundnarayanamurthy 2 жыл бұрын

Good job brother, you are really crisp and articulate with your thought process and approach towards explaining things. Wish you success , cheers 🥂

@bd3723 3 жыл бұрын

Best description on tries ever! I've watched other ones but they were more complicated for some reason

@AlgosWithMichael 3 жыл бұрын

Thank you!

@Anubis10110 3 жыл бұрын

Very calm, easy and straight forward explanation.. thanks

@msadityakumar1 Жыл бұрын

Thanks Michel, the video was so good that I could write a Trie DS myself within 20 mins.

@harungumus6512 2 жыл бұрын

Great explanation. Simple and plain.

@disantha4447 3 жыл бұрын

I've always find your videos are useful...Great Explanation....This channel deserves more subscribers..

@AlgosWithMichael 3 жыл бұрын

I appreciate that, I try to put a lot of effort in my videos!

@shidajieqing 3 жыл бұрын

How I didn’t discover you sooner, your explanation is the best!

@arvindmega 3 жыл бұрын

Great explanation. No more time than it needs to take to explain the DS. Awesome work dude. Keep it up.

@AlgosWithMichael 3 жыл бұрын

Much appreciated!

@JLRide 2 жыл бұрын

Thank you Michael. You made this easy to understand. Thank you.

@__--_--_----- 3 жыл бұрын

this is incredible, fantastic work Michael

@AlgosWithMichael 3 жыл бұрын

Thank you!

@gautamtyagi8846 2 жыл бұрын

many many thanks bro! amazing explanation and easy to comprehend.

@sumodbadchhape9823 3 жыл бұрын

Really great explanation. Now I feel confident that if I get a question on trie I can easily implement it.

@AlgosWithMichael 3 жыл бұрын

Awesome!

@fatihucar5842 Жыл бұрын

very useful approach

@AerosDaDinoHoodie Жыл бұрын

Very good explanation, thank you!

@harpercfc_ 2 жыл бұрын

Awesomeeeee! Thank you so much Michael

@AlgosWithMichael 2 жыл бұрын

No problem

@ruthraramanan3407 3 жыл бұрын

Congrats bro!! You've actually made me understand smthg!

@AlgosWithMichael 3 жыл бұрын

Haha awesome!

@chelseaip759 3 жыл бұрын

Thanks for being such an awesome source

@AlgosWithMichael 3 жыл бұрын

My pleasure!

@richequan5115 2 жыл бұрын

very helpful, thanks Michael!

@rembautimes8808 3 жыл бұрын

Wow, I'm watching this on Sat morning as a warmup exercise to my coding routines. Amazing in its simplicity, coherence and how the author went straight to the point.

@shahinkohzadpour Жыл бұрын

it was nice ; thanks Michael !

@jaybhatt6775 3 жыл бұрын

dude ur a fucking great teacher, do you know that? love you brother!

@SaikiranDasika 2 жыл бұрын

Great explanation!

@AlgosWithMichael 2 жыл бұрын

Glad it was helpful!

@intcoder Жыл бұрын

👏Great explanation and great coding!! Thanks.

@ooflajboo 3 жыл бұрын

earned yourself a subscriber. legit video

@AlgosWithMichael 3 жыл бұрын

Thanks Ben!

@sajankumarsingh7536 3 жыл бұрын

Thank you bro for this video.

@hawaijarjs7496 3 жыл бұрын

Thanks Bro! You made my day 🤘

@AlgosWithMichael 3 жыл бұрын

Glad I could help!

@sachinmagdum 2 жыл бұрын

Good one! Small optimization/correction - char c at each Node can be removed (not needed).

@sachinmagdum 2 жыл бұрын

@John Gelson you don't. Isn't the location (index) in (Node[]) array represent the letter (ASCII value) itself?

@airbus5717 2 жыл бұрын

thanks for this super useful video.

@TroyKuang 2 жыл бұрын

This is amazing, thank you!

@AlgosWithMichael 2 жыл бұрын

No problem 😊

@apurvasharma7660 3 жыл бұрын

You are doing a great job. You are maintaining the quality of the contents. Could you add some detailed videos on tries?

@AlgosWithMichael 3 жыл бұрын

Yea, I can definitely do more Trie videos. Thanks for watching!

@debrajmaji9608 3 жыл бұрын

Subscribed you!! thanks for the great explanation.

@emreimamoglu6367 2 жыл бұрын

Thanks for this great video :)

@architshinde3977 3 жыл бұрын

Thanks a lot! This was really helpful!

@AlgosWithMichael 3 жыл бұрын

Glad it helped!

@sininsterme797 3 жыл бұрын

This was very helpful. Thank you.

@AlgosWithMichael 3 жыл бұрын

Of course!

@andriys5772 3 жыл бұрын

Thank you so much!

@AlgosWithMichael 3 жыл бұрын

No worries!

@huseyinbarin1653 Жыл бұрын

Thanks, very clear explanation. "isWord" flag is fucking awesome, you can hold two words in the same path like cat and cats. With this flag when we search "cat", it will return it as true.

@UCS_RheaRaviSharma 3 жыл бұрын

Amazing video!!!

@AlgosWithMichael 3 жыл бұрын

Thank you!

@riadas7721 2 жыл бұрын

Awesome. thanks!

@AlgosWithMichael 2 жыл бұрын

Of course!

@OllytheOzzy 3 жыл бұрын

Thanks mate

@AlgosWithMichael 3 жыл бұрын

Anytime :)

@lewisbrowne8799 3 жыл бұрын

nice one mike good vid.

@AlgosWithMichael 3 жыл бұрын

Thanks dude!

@pramodsharma4508 3 жыл бұрын

This guy never disappoints...

@AlgosWithMichael 3 жыл бұрын

Hahaha I appreciate that, thanks for watching!

@ishq_gunah_hai3179 3 жыл бұрын

Seriously never ❤️

@AlgosWithMichael 3 жыл бұрын

Haha thank you!

@aryan7069_ 2 жыл бұрын

Amazing

@shankarregmi 3 жыл бұрын

Great Video

@AlgosWithMichael 3 жыл бұрын

Thanks!

@ameynaik1755 3 жыл бұрын

This is neat! Can you please do a video on Design Search Autocomplete System

@altayhunoglu1709 3 жыл бұрын

You have a new subscriber :)

@AlgosWithMichael 3 жыл бұрын

Welcome aboard!

@EinPiannist 2 жыл бұрын

Hi! Thanks so much for this video. Could you please tell us what kind of keyboard you use lol

@vbmendes 3 жыл бұрын

Very good content. Just for the sake of contribution, I found out that the property 'c' in your node is actually not needed. You can surpress it without losing information in your structure. This information is already there in the children array of nodes.

@AlgosWithMichael 3 жыл бұрын

Ah good point, thanks for that!

@soniahandle 7 ай бұрын

Great video! If we wanted to add a delete method, would we just getNode and then set isWord to false?

@frankdaniel3506 2 жыл бұрын

Which software are you using for explanation?

@maherworld1 2 жыл бұрын

Hey Michael, i really liked your explanation, but i have a question regarding using array and intializing its length, does this affect space complexity since we take 26 spaces in memory every time we insert one character ? thats why using a hashmap is more efficient, though i really prefer this solution because its cleaner and easier to understand, thanks again

@antonfernando8409 2 жыл бұрын

Nice, just 2 questions, do you really need that array of [26], i mean it seems like a waste of resource, b'c the Node itself as has 'c', so a ten letter word would have 10 nodes, no need to utilize an array[26]. Lastly, why not utilizes recursion at some point. Thanks, I am bit out of touch with tree structures and recursion, not since college have to implemented them, so would appreciate a broad answer, thanks.

@jcanbb 2 жыл бұрын

Anyone able to provide some input on what (if any) the performance difference would be between creating looping over char c : word.toCharArray() versus looping over the string via an index variable and extracting the char at each iteration with char c = word.charAt()?

@rickyc46 11 ай бұрын

it's a great video! Very clear explanation. I was just curious why you used an array for children Nodes instead of a map? Is it just your preference?

@mr.morshedloo408 3 жыл бұрын

Hi could you help me about Multi-index Hybrid Trie for IP Lookup and Updates?

@MrAbhitv 3 жыл бұрын

Hey Michael, i got a question. At line 15-16 (In insert method) i don't understand what happens if curr.children[c-'a'] is not equal to null. If we are inserting Strings, for example ,st1= "Apple" and st2 = "Add" how can A point to P and D at the same time. When we are inserting "ÄDD" Since curr.children[a-'a'] != null. It moves to Node with value P. A new node for D is not created. Thanks.

@AlgosWithMichael 3 жыл бұрын

The way characters point to other characters is each node has a `children` array of nodes representing all possible characters in the alphabet. If the index at `c - 'a'` evaluates to null, that means a new node needs to be created at that index. Hope that helps!

@lean.drocalil 2 жыл бұрын

One issue I noticed there is in case someone passes an ASCII entry above 'z', program is going to attempt to access an invalid index into its array. Either checking or making it wrap around with remainder of division by 26 is required to prevent that.

@adamandom 11 ай бұрын

true, but this specific problem states that we can assume that all chars will be between a-z

@szymon200000 2 жыл бұрын

For the most part I get the video, but I can't seem to figure out why in the return statement in 'search(String word)' has to include 'node != null.' I got rid of it and it passed the 'Run Code' test but not the submission itself E: nvm. it's because 'curr' can point to a null spot in the array in the case that a prefix is not found in the trie. 'null' doesn't have any methods, but it doesn't give you an error because of short-circuiting. it sees null IS null and just spits out 'false' without checking 'null.isWord()'

@sunnilabeouf 3 жыл бұрын

Instead of having an array of length 26 defined for each node, you could just use a set for each node and add it’s children using a character -> node key value pair

@AlgosWithMichael 3 жыл бұрын

Yep you can do that as well 👍

@thivyamathias3947 Жыл бұрын

Is there any specific reason to have Node as inner class??

@Kidpunk98 2 жыл бұрын

Fantastic video! thank you so much! You really are an amazing teacher. my only question though is why did you need a char member variable in your Node class. I wrote mine and noticed the data structure operates perfectly fine without that "char" member variable in the Node class.

@kevinfischer4209 2 жыл бұрын

Amazing fact

@sachinbisht7417 3 жыл бұрын

I got a question in like if we want to print the vertices by numbering the edges in order of insert ....how can we do this... for example 1 : input - 1 ABC output - 0 -> 1 A 1 ->2 B 2 ->3 C for example 2: input 3 AT AG AC output - 0 -> 1 A 1 -> 4 C 1 -> 3 G 1 -> 2 T THANKS FOR HELPING.....

@AlgosWithMichael 3 жыл бұрын

Hmmm tough question

@sudipkumardey8791 Жыл бұрын

LMAO, The kids yeeeaaah voice 🤣🤣🤣

@micknamens8659 2 жыл бұрын

Optimization of space requirements: It seems that we don't need the instance variable 'char c'. And the boolean variable 'isWord' could be avoided if we have 2 classes: 'Node' with method 'isWord()' returning false, and a subclass 'EndNode' which overrides 'isWord' now returning true. Instead of setting the variable value, we replace the object (once).

@xxsanyxx1 2 жыл бұрын

I have a question! I'm getting a index out of bounds error at line 36, if(curr.children[c - 'a'] == null) return null; Can someone explain why it might've happened?

@AlgosWithMichael 2 жыл бұрын

Is it possible your character 'c' is not a lowercase letter?

@xxsanyxx1 2 жыл бұрын

@@AlgosWithMichael I've double-checked and it is a lowercase letter. Not too sure what's wrong with it! Also, thank you for the great explanation in the video! :)

@LyricVista 3 жыл бұрын

from where i get he full code?

@AlgosWithMichael 3 жыл бұрын

I don't have it posted anywhere :/

@omarsharim6253 3 жыл бұрын

Why your search is O(1) if you have a search function with an iteration through N letters, think you are doing a linear search, so i think your search it's O(N), any thing im missing?

@AlgosWithMichael 3 жыл бұрын

Space complexity is O(1), time complexity is O(N)

@omarsharim6253 3 жыл бұрын

@@AlgosWithMichael Got it, ty

@sunebarnard9043 2 жыл бұрын

Could someone maybe explain again why 'a' is subtracted from the char? Just a little confused there...

@AlgosWithMichael 2 жыл бұрын

It is because 'a' in ascii is 97 in its decimal value. Any lowercase letter minus 'a' will give you the index of the letter. So as an example, say I want to get the index of 'b'. 'b' has a decimal value of 98 (1 more than 'a'). So we subtract 'b' - 'a' and that gives us 1 as the index. 0 is index 'a', 1 is index 'b', etc. Hope this makes sense!

@sunebarnard9043 2 жыл бұрын

@@AlgosWithMichael thanks that helps a lot 😊

@ashishjaswal1437 2 жыл бұрын

//Search Insert and Delete are discussing Below public class Implementation{ static class Node{ public char c;//We are dealing with only small values; public boolean isWord; public Node[] childern;//Store all the childerns in this Node. Node(char c){ this.c = c; isWord = false; childern = new Node[26]; } } static class Trie{ private Node root; public Trie(){ root = new Node('\0'); } public void insert(String word){ Node curr = root; for(int i=0;i

@kumarGobika-xm3ur 4 ай бұрын

Which language is this?

@dmstrat 2 жыл бұрын

Just came across this ... good work and nice graphical instruction. I do have a concern over the "StartsWith(prefix)" method as it does not work as I would expect. In your implementation, If you have the word 'cat' in the trie but not any other word beyond that, like 'cats' or 'catastrophe' your StartsWith('cat') would return true even though you have no more words beyond that point. Therefore, a subsequent Search('cats') or any Search/StartsWith('cat' + any character(s)) would return false. I would expect the StartsWith to check to be sure there are nodes in the children array to indicate a longer word is available in your trie. Example: 'cat', 'cats', and 'catastrophe' were inserted to the Trie and performing a StartsWith('cat') would return true because there are more nodes below 't' Example 2: 'cat' was inserted to the Trie and performing a StartsWith('cat') would return FALSE because there are no children nodes below 't' What are your thoughts?

@ivaylopankov7369 3 жыл бұрын

Great video! For the purposes of this question though, the information about the exact character inside a node is not needed.

@AlgosWithMichael 3 жыл бұрын

True, thank you so much for watching!

@christowndotcom 2 жыл бұрын

Ah, since the children have an array of the alphabet anyways, the actual c element of the Node class is not needed. Just FYI. Thanks!

@AlgosWithMichael 2 жыл бұрын

Yea, that is a good point! Thanks for watching

@nishantparmar 2 жыл бұрын

Great and very simplified... But small correction in insert method public void insert(String word) { Node current = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (current.children[c - 'a'] == null) { current.children[c - 'a'] = new TrieNode(c); current = current.children[ch - 'a']; }else if(current.children[ch - 'a'].c == c){ current = current.children[c - 'a']; } } current.isWord = true; }

@jamesblack2719 3 жыл бұрын

Why is Node a class instead of a struct? You will have many nodes and a class requires more memory than a struct. You are also using "c - 'a' " in a loop. Put that into a variable and do the calculation once. Why pay for the calculation over and over. You didn't use the term ASCII, which is surprising, as it may help viewers to understand that this is the case. Why not make this recursive, rather than using so many for loops. At the end a trie is just a modification of a binary tree, but it can have 26 children. Nice video though.

@AlgosWithMichael 3 жыл бұрын

Yea, I could have put c - 'a' in a variable. I think using loops is easier to understand than recursive approaches, especially if I am trying to explain a concept that people don't know already. Thanks for the feedback!

@jamesblack2719 3 жыл бұрын

@@AlgosWithMichael Thanks for the reply. If you just mentioned that there are other options that would be enough. My concern is people will look at your video, then just copy it and not realize that it not the best choice, as this was written to teach, not for production. This happens when people put snippets of code on StackOverflow also.