LESSON 05 OF 08Trie · insert & search
0% learnt
TRIE INSERT AND SEARCH · PREFIX TREE
After inserting “cat”, what should inserting “car” do with c → a?
Tries compress common prefixes. The path c → a already exists and must be reused.
RULE TO APPLYFollow one edge per character; success requires both a full path and an end marker.
LIVE ALGORITHM STATEc → a is shared; only the missing r branch needs to be created.
INSERT “car”
car
LESSON 051 / 2
REAL INTERVIEW PROBLEMStore many words by sharing their prefixes.
Build a trie that inserts words and searches for complete words. A prefix path alone must not count as a stored word.
INPUTinsert("cat"), insert("car"), search("ca")OUTPUTfalse
WHAT YOU WILL DOReuse shared character paths, create only missing branches, and set an end-of-word marker at the final character.