Implement Trie (Prefix Tree) - Leetcode 208

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@evalyly9313]

This is the best Trie introduction video I watched in youtube, very clear and concise. Bravo!

[@ARkhan-xw8ud]

watch striver series

[@sucraloss]

You legitimately explain these concepts better than any professor I've had, and I went to one of the most highly regarded schools in the US for Computer Science. You outdid both the professors and their teaching assistants. You have a gift for explaining this stuff.

[@sanjanar9198]

Never thought Trie would be this easy to understand, thanks a lott!!

[@sprajosh]

I avoided trie for so long thinking it will be difficult to understand. Thanks for this. This was very easy.

[@niravarora9887]

I am with you on this, hahaha

[@z7847]

Neetcode really saving the day here. I watched other videos, but none explained and illustrated how to code it efficiently. Your drawing is so helpful and the clean, simple code makes sense. Thanks Neet!

[@starboi_6]

I am usually struggling with new data structures, but you made it simple and smooth. Tanks for the great video.

[@sravanikatasani6502]

Thank you so much!! I have learnt a new data structure today..

[@aaab45357]

A note on implementation: instead of a python class representing the node, you can simply represent each node as a dictionary of chars to dictionaries and use a placeholder (like '$') to mark the end of a word. This will be more efficient (same big-O, though) in python in both memory and time, for you are not wasting a bunch of space pre-allocating lists, you are not having to deal with python's overheads and, most importantly, you would be using a highly optimized python data structure calling c under the hood. On top of all of that, you get a cleaner implementation

[@GinsuGames]

I think the class approach is much cleaner to read

[@Kokurorokuko]

@@GinsuGames yeah, and it works for any kinds of strings

[@elias043011]

Great explanation! The very important take away here was that you mark the end of a valid word with the TrieNode variable, otherwise "appl" may look like a valid word after inserting "apple"

[@bugracansefercik917]

Thank you for the great video. If assume words are ending with a certain character like '.'. There might be a shorter and simpler solution: class Trie: def __init__(self): self.trie = dict() def insert(self, word: str) -> None: curr_trie = self.trie for l in f'{word}.': if l not in curr_trie: curr_trie[l] = dict() curr_trie = curr_trie[l] def search(self, word: str) -> bool: return self.startsWith(f'{word}.') def startsWith(self, prefix: str) -> bool: curr_trie = self.trie for l in prefix: if l not in curr_trie: return False curr_trie = curr_trie[l] return True

[@kritmok1875]

never thought that I would get the best trie introduction video in a leetcode video. Thanks for the great work!

[@hmanjun7260]

Using a hash map was genius. Once I saw that, I went and redid my code before looking at the rest of ur solution

[@Xavierrex3]

Man your videos are incredible, and I've learned so much about programming in general just from your channel. Before this I was stunned about how to approach problems like this or dynamic programming but just from following solutions and understanding the concepts better I can do problems like this moderately well now

[@tapasheetabassumurmi1895]

I am getting addicted to this channel!! Thanks God!! You've sent this man for us!

[@WalterGordyCanada]

These videos are literally better than the courses I took in University. Thank you!

[@nou4605]

The code is marvelously simple considering how useful of a data structure this can be.

[@1-ov947]

You are the best leetcode teacher on entire KZbin!

[@iugaialeksei2108]

OMG, man, you possess a special talent to explain complicated things smoothly and simple. I'm a big fan of your channel!

[@rkkasotiya]

Simplest video to understand Trie and implement it. Keep up the good work.

[@BobbyMully]

When I did this one before wathcing the video, my code was double the length of yours. Nice solve!

[@tjsm4455]

Good explanation. After understanding the logic I implemented the code myself. Feels good.

[@seanjcan]

Best explanation of Tries I have come across so far. Bravo!

[@lymmontijo87]

Thank you!! I had never seen tries and had been avoiding it. Its actually quite easy.

[@Dhruvbala]

This was one of the more enjoyable problems I've done

[@nhuphan7112]

honestly just want to say your videos been great in my interview prep :) (totoal newbie at leetcode)

[@Manu-et6zk]

please explain time and space complexity after u solve the problem

[@juliacheng4751]

Time is O(n*m) for insertion (n is the number of words, m is the max len), O(m) for search. Space is O(n * m)

[@Kokurorokuko]

@@juliacheng4751 I think you're incorrect. Time complexity is O(m) for insertion. Space complexity is O(m).

[@deniyii]

A more useful and challenging problem would be to return a list of words that starts with a given prefix. Pretty much autocomplete. I’m not sure if that one can be solved iteratively though, I’ve only seen it done recursively.

[@vashishtgupta7416]

I haven't seen better tutorials than yours for LC problems anywhere! Great work :)

[@reddev9143]

Thank you so much! Just can’t tell how cool and valuable your videos are! Keep’em coming!

[@unanimous8510]

What an amazing explanation for the guy who just started learning tries 👍

[@antonyndungu5514]

I have watched a few explanations on the tries, this is the best. Keep them coming at least for now you don't have a job

[@TechOnScreen]

dude he is in google !.. someone truly said. Time is mightier than fate..

[@antonyndungu5514]

@@TechOnScreen Yah, I knew with his level of skills its just a matter of time and he will get one of those top jobs in the industry

[@TechOnScreen]

@@antonyndungu5514 yeah dude.. hope some day we will have our luck too 😂

[@antonyndungu5514]

@@TechOnScreen True, can't wait for that :-)

[@Z00keeper54]

Minor gripe (at least for the JavaScript version) - the constraints indicate that word and prefix have to be at least 1 lowercase English letter, but when you go to submit, the test tries passing in empty strings.

[@saumyatyagi8768]

This is the best Trie vid so far ! Excellent explaination . 👍

[@Lmcrf]

you don't need to create additional TrieNode class, just initialize everything in TrieNode class into Trie class. and replace every cur = self.root by cur = self and it works fine i don't know why, this new solution was much faster, may be it was leetcode bug

[@saisagarsharma]

Dude i have been postponing this DS for an year thinking its going to be very tuff. U just confirmed it to be wrong in first ten mnts. Great job man!

[@noa.leshem]

Super helpful videos. Been looking at them a lot.

[@NeetCode]

Thank you so much 🙏

[@rishiraj3521]

Always love the way you explain things so easily and concisely.

[@changlingao4609]

thank you so much! such an awesome explanation of Trie you make everything so easy to understand thanks!!

[@harishkandan7910]

Hey, what if we insert a substring of an already existing string. Say we insert 'app' when 'apple' already exists in the Trie. Wouldn't that make the second 'p' in the 'apple' also an 'endOfWord' making the 'le' in 'apple' inaccessible?

[@kamaleshs5324]

No harish, because you will only be checking for the endOfWord condition when you have reached the end of the particular word you are searching for, say you are searching for apple and both the second p and the e are marked as endOfWord, then when you are searching for apple, you iterate one by one, a, p, p, l, e and after reaching the end point, only then you check for the endOfWord Condition. In case you are searching for app, then you iterate through a, p, p and then check whether the currentNode has endOfWord as true, in this case yes, so both app and apple are accessible.

[@DeGoya]

@@kamaleshs5324 that doesn't answer the question though, since he asked what will happen if "we insert a substring of an already existing string"

[@torin755]

No, it will not be inaccessible, simply because if you look again at the search function you will see the for loop runs down the tree for the length of the searched word REGARDLESS of if it finds a node with EndOfWord. Only AFTER it has gone down the length of the word, will it check if the node it LANDS on is EndOfWord=True. I.e it will NOT stop just because it found an EndOfWord, but instead traverse the word's chars entirely and then check if the node it lands on is EndOfWord=True

[@janeikeliu]

Thank you! Your explanation of of the trie data structure is so clear!

[@RobinHistoryMystery]

thanks! I thought Trie is gonna be super hard, nice explanation

[@krutimody91]

Omg this is amazing, I have been trying to understand this for an hour now - finally I get it! Thanks!

[@killeraloo3247]

Loved the easy to understand explanation. 🧡 from remote.

[@sudharahul2010]

Great practical explanation of Trie!!

[@symbol767]

My favorite data structure, I just came to make sure my code was as good as the one you show, and its exactly the same thankfully. Thanks for your videos Liked!

[@yakeensabha655]

what's the complexity of search, insert, delete the word in the trie? when it's implemented using a 26 array? I'm tryna guess it? the search and insert is O(L which is the length of the word)? the all space is 26 * the number of all nodes? plz I need to know

[@smartsoothing776]

If you could have explained all the data structures like this before, My life would have become easier..

[@qR7pK9sJ2t]

But did you come earlier to get his help is the question that I want to ask from you ?

[@YunChiehChiu]

Thank you so much. Your videos makes everyday learning a feasible plan. Your explanation makes every single problem lots more easier to understand and reduce my imagination to the difficulty of the problem.

[@diplodocus3]

skimmed through 3-4 blah blah videos, this finished the job gracefully

[@murtuza.chawala]

The best Trie Explanation

[@noctua7771]

After your explanation I was able to code it in under 2 mins without looking back at the video. You sir are an absolute legend.

[@osamaayman3765]

I had no other option but to like this implementation! Thanks Kevin :)

[@shreshthkaushik-hu8bz]

I solve all these questions myself after looking at how neetcode solved it and then add more commenting, name styling to make it even more easier to read ( Hopefully atleast ) """ The way we can solve this question is by creating a data structure called "TrieNode" with two attributes -- children and end. children detonoes a map of maps where we would put each our letters and as we reach the end of the word, we mark that letter as ending using the "end" attribute """ # Create a class to store the letters in form of a tree class TrieNode: def __init__(self): self.children = {} self.end = False class Trie: def __init__(self): # Initialize the TrieNode instance self.root = TrieNode() def insert(self, word: str) -> None: # Set the current pointer to the root of the tree curr = self.root # Go through each letter in the word and add that into the tree if not already for letter in word: if letter not in curr.children: curr.children[letter] = TrieNode() curr = curr.children[letter] # Since by this time, we reach the end of the word so mark the letter as end curr.end = True def search(self, word: str) -> bool: # Set the current pointer to the root of the tree curr = self.root # Go through each letter and keep going down in the tree to find if this word has been # created for letter in word: if letter not in curr.children: return False curr = curr.children[letter] # If at the end we have the letter marked as end then yes it exists return curr.end def startsWith(self, prefix: str) -> bool: # Set the current pointer to the root of the tree curr = self.root # Go through each letter and keep going down in the tree to find if this word has been # created for letter in prefix: if letter not in curr.children: return False curr = curr.children[letter] # if we never returned false, means this is the prefix or the entire word return True

[@mruduladdipalli5417]

A Big Salute To You Bro, for the solutions and great explanation , I have recommended this channel to at least more than 3 people 🙌

[@ambermichellemartinez]

Thank you, the best trie explanation! You're amazing!!!

[@keremserttas5898]

What is the worst case time compexity? Is it exponential? If it comes .........

[@janvidalal476]

this guy is making our life play on easy mode

[@yuenyiupang]

Very good explanation, but can someone tell me which way is more efficiency(if we dont care space) on above case, Trie, or a hashmap include all combination app become a = [app], ap = [app], app = [app], and 1 more hash for just store the word, as latter way can ensure search and startwith run O(1) time?

[@sirmidor]

Yes, you can achieve average O(1) for searching and startsWith this way, though your insert will be slower. For a word of length m, I believe it'll be be O(m^2): you'll be adding m strings, obtaining those through list slicing, which is O(slice length). Average slice length is about half the length of the word in this case (for a word of length 4: 1st prefix is length 1, second is 2, third is 3, last is 4), so m * m * ~0.5, which is O(m^2). Doing it this way could be better if you inserted rarely, but searched and used startsWith a lot. You said not to care about space, but this is more space-efficient as well as a hashset is a built-in optimized data structure, while a TrieNode is an entire user-defined class instance.

[@8nehe]

Great simple explanation

[@amitrastogi1405]

Very well explained. Thanks!

[@MP-ny3ep]

You are a godsend. Thank you sooooooo much for all your work 🙏🙏

[@harrywang9375]

It should be mentioned that marking Apple as the end of the word is not just to be safe. Your function would return false for not found if your word search was searching for both Apple and Apples if you didn't have that boolean to check if it was the end of the word. If Apples existed for example, then the E in Apple would no longer be the end of the chain. Despite that fact, Apple is a very legitimate word even though it has a child node in 'S'.

[@mohammedfahadnyc1385]

when you enter apple, it will mark e as the end of the word, then again when u enter apples, it will run for the length of apples, and add s after e. Then if u search, u will get True for both. Just because a node is marked end = True doesnt mean u cant access or add to that Node.

[@vjnvisakh]

simple and smooth

[@elachichai]

crisp and clear

[@TejaDuggirala]

You are literally making my life easy. Thanks man 🙏🏻

[@illu1na]

Do we have to use trieNode? I used dictionary and had "None" to mark if the node is at the end.

[@vivitra1022]

Thank you very much for the very clear explanation!!!

[@davi_paula]

Amazing explanation, great job!

[@vishalrao5202]

Beautifully explained 👏🏻👏🏻👏🏻

[@Joseph-ub7rh]

My assumption for runtime complexity is O(n) where n is the number of characters in the string that we are inserting or searching for. Now for space complexity, it seems to me that it is O(n^n) because each node can have n children.

[@hillarioushollywood4267]

not n nodes can have n children, you can say, 26 chars can have n children :) That Means, O(n+m+k+.........26th l)

[@hamoodhabibi7026]

@@hillarioushollywood4267 So this is Space: O(n * 26) where n is the length of our word and each character in our word can have 26 children max

[@princeanthony8525]

Can you code up the delete functionality as well ?

[@MinhNguyen-lz1pg]

Awesome explanation my man!

[@ameynaik1755]

Neat video! Please do a video on Design Search Autocomplete System.

[@shravancheekati9045]

Why create an additional TrieNode class? Why not just put them in Trie?

[@wallaby28]

Brilliant explanation

[@phantomsedge5686]

This is a slow method. Is there a faster way?

[@farshadsaberi2740]

Thank you very much for clear explanation and truly neat code :)

[@bhabishyachaudhary3495]

really helpful thank you so much.

[@madanmohanpachouly6135]

Real cool explanation, Thanks Man.

[@codeUrDreams]

Brilliant! Thank you so much!

[@carloslazarin]

Excellent explanation!! thank you a lot!

[@travellercoder7298]

Sir i have a doubt that in apple it's two p's and since we inserted the first so will it insert the second one?? Plzz explain

[@atharhussain6534]

Data structure look like for letter apple : {"a":{"p":{"p":{"l":{"e:{}}}}}

[@veedhiabhhirram4121]

best video out there

[@introvertwhiz-ll2ip]

Ok I am a full stack developer currently grinding on leetcode. I just don't understand why you don't share code on github. If you have shared then provide the link. Thank you so much for you explanation.

[@oliver1231033]

what if we insert a word "super" and then a word "superman", is that gonna cause any problem when we are searching?

[@mohammedfahadnyc1385]

No. For super, search function will run the loop for len(super), and at r, it will see its marked end of word, so it will return True. For superman, it will run len(superman), so when it comes to r, it will just check if r exists, then move to move to a and move to n, when it reaches n, it will check if endofword is true, and return True. So it wont be an issue, the whole idea is we traverse by the length of the word, so no issue will arise

[@LongVu-sm8wm]

a great explanation !. Thanks

[@wajahatali6403]

Excellent video, as always.

[@aspiretechie1191]

You are a GOAT Man..........

[@MichaelShingo]

yess!! tries are cool

[@Michalr1223]

Great explanation! thank you :)

[@jasonahern3498]

Thank you! Great video

[@KrzysztofKoziarski]

Thanks

[@dorondavid4698]

Nice explanation!

[@AnnieBox]

what's the time cost of the solution? Is it 26*len(word)?

[@NeetCode]

Yeah that's correct!

[@ashs3979]

You’re awesome dude ty

[@deformedzebraonbike]

I have big interview tomorrow. Your videos have helped me a lot, fingers crossed!

[@itachid]

How did it go?

[@ruzaikr]

Thanks!

[@XxM1G3xX]

Wouldn't it be better to just add another empty value node at the end of a word to designate the ending? instead of adding another variable to every single node? You would just check if after the 'e' for apple there is an empty node vs i.e. an 's' node for apples, this way you would know if apple vs apples exist. I mean for consistency this would make more sense since you are adding an empty node for the 'root' instead of adding another variable for 'stringStart'. Edit: I saw your solution of adding a hashmap for value and node, instead of having two separte char and object for each node. This would complicate things with what I said because you cannot use an empty key in a hashmap IIRC.

[@servantofthelord8147]

Excellent.