DSA Lab
Trie
A trie stores strings one character per level, so words that start the same share their first nodes. A word is a path from the root, ending at a node marked as a word end.
Trie: how it works
In this tool: prefix tree, autocomplete. Put in your own values and watch it change. Each operation runs one step at a time and says in plain words what happened, with its calculation worked out. The code is shown in Python, C, C++ or Java with the line that just ran marked, and an Understand it panel gives the idea, why it works, the cost of each operation, common mistakes and a short quiz.
Lessons that use it
- Tries: prefix trees (Data Structures)Store words letter by letter in a tree, so finding a word, or every word that starts with a prefix, costs only the length of the word.
- Routers and forwarding tables (Networks)How a router chooses where to send each packet: forwarding tables, the longest matching prefix, and the default route.