Implement Trie Prefix Tree | implement trie prefix tree | implement trie prefix tree leetcode

**Complexity Analysis**
For all 3 methods i.e. insert, search, and startsWith
Time complexity: O(m), where m is the word length.

SUPPORT MY WORK BY SUBSCRIBING TO THE CHANNEL :

[shubhamsingh]

great explanation bro
please keep up the good work

[darshank]

God bless you for your way of explaining.
Thank you so much.

[kibuikamwangi]

Good job i thought trie were difficult! So simple precise yet detailed explanation plus implementation

[ian_senior]

thanks for the video. helped me out a lot. i modified your code a little to use a helper function eliminating duplication.

class Node {
char letter;
Node[] nodes;
boolean end;
Node(char letter) {
this.letter = letter;
this.nodes = new Node[26];
}
}
class Trie {
Node root;
/** Initialize your data structure here. */
public Trie() {
this.root = new Node('\0');
}
/** Inserts a word into the trie. */
public void insert(String word) {
traverse(word, true).end = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Node node = traverse(word, false);
return node != null && node.end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return traverse(prefix, false) != null;
}
public Node traverse(String word, boolean insert) {
Node node = root;
for (char c : word.toCharArray()) {
if (node.nodes[c - 'a'] == null)
if (insert) node.nodes[c - 'a'] = new Node(c);
else return null;
node = node.nodes[c - 'a'];
}
return node;
}
}

[cloud]

Wow, this question is actually super easy after your explanation! Thanks man!

[salimzhulkhrni]

Precise explanation.. keep up the great work :)