04. Trie DS & Implementations

Trie DS ?

A trie is a tree-like data structure whose nodes (it can have N no. of nodes) store the letters of an alphabet. By structuring the nodes in a particular way, words and strings can be retrieved from the structure by traversing down a branch path of the tree.

---

General overview on TRIE DS formation

Remember : Every Node has 26pointers (for each alphabets) although they are not shown here.

---

What's in a Single Node of Trie ?

---

Insertion of Words in a Trie

public void insert(String wrd) {
		Node curr=root;
		for(char c: wrd.toCharArray() ) {
			if(curr.next[c-'a']==null) curr.next[c-'a']=new Node(c);
			curr.next[c-'a'].count++;
			curr=curr.next[c-'a'];
		}
		curr.isEnd=true;
	}

---

Video Reference

Implementation of Trie using Array.

Implementation of Trie using HashMap.

Trie using HashMap give you the edge in inserting any string containing any character over Trie using Array + Trie using HashMap has less space complexity.

---

THANK YOU