# Tries

###
JB
*Updated on *
・2 min read

CS Level Up Series (28 Part Series)

1) CS Level Up Series Introduction
2) Dynamic Arrays
3 ... 26
3) Linked Lists
4) Stacks
5) Queues
6) Hash Tables
7) Binary Search Trees
8) Binary Heaps
9) Priority Queues
10) Graphs
11) Tries
12) Binary & Bit Manipulation
13) Common Sorting Algorithms
14) Searching Algorithms
15) Permutations, Combinations, & Subsets
16) NP-Complete & Fibonacci Heap
17) Detecting Graph Cycles With Depth-First Search
18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Finding Articulation Points & Bridges in Undirected Graphs
21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Checking If An Undirected Graph Is Bipartite
23) Extending An Iterator
24) Union-find (Disjoint-set)
25) Minimum Spanning Tree (Kruskal's Algorithm)
26) Sliding Window Technique
27) String Searching Using Rabin-Karp
28) Fenwick Tree (Binary Indexed Tree)

## Resources

- Trie Overview
- Trie Overview + Implementation
- Trie Operations + Implementations
- In Depth Trie Explanation
- A good implementation of the delete operation

(Also worth mentioning is this article from the Visual Studio Magazine. The article explains tries and why you might want to use them.)

Takeaways:

- A
**trie**is an ordered tree that compactly stores strings. Each**node**in a trie represents a single character in a string. Say we store the words "car" and "cars" in a trie - the trie would only use four nodes for both - one for each distinct letter of the words (c,a,r,s). - They are also known as
**digital trees**and**prefix trees**. - A trie is most efficient when it is storing strings with similar prefixes, but in general tries are usually not space efficient. They have a space complexity of
*O(n + k)*. - They are useful for queries involving string prefixes, such as suggesting the next character(s) for a given prefix.
- Tries are not usually found in standard libraries of popular languages (Java & C#, for example, do not have a trie data structure).
- Tries are typically implemented using arrays or hash tables.
- Although hash table implementations are more flexible, array implementations can be more efficient by placing limitations on the trie (like only allowing characters a-z)
- Many trie implementations will use booleans to mark the end of words/strings. But some implementations will use an additional node appended after the last character of the word. This additional node might contain a
`NULL`

value or a special character. - Similarly, the root/head node of a trie can be represented in various ways. For my implementations I used a special character (
`$`

) to denote the root node. - Inserting and searching are both
*O(k)*operations. - A related data structure is a
**radix tree** - Radix trees are basically a space efficient trie. A trie only stores one character per node, whereas a radix tree can store many. A radix tree is essentially a trie where all nodes that are the only child are merged with their parent nodes - this means less total nodes are required for the same number of words.

Below you will find some common bit manipulation

As always, if you found any errors in this post please let me know!

CS Level Up Series (28 Part Series)

1) CS Level Up Series Introduction
2) Dynamic Arrays
3 ... 26
3) Linked Lists
4) Stacks
5) Queues
6) Hash Tables
7) Binary Search Trees
8) Binary Heaps
9) Priority Queues
10) Graphs
11) Tries
12) Binary & Bit Manipulation
13) Common Sorting Algorithms
14) Searching Algorithms
15) Permutations, Combinations, & Subsets
16) NP-Complete & Fibonacci Heap
17) Detecting Graph Cycles With Depth-First Search
18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Finding Articulation Points & Bridges in Undirected Graphs
21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Checking If An Undirected Graph Is Bipartite
23) Extending An Iterator
24) Union-find (Disjoint-set)
25) Minimum Spanning Tree (Kruskal's Algorithm)
26) Sliding Window Technique
27) String Searching Using Rabin-Karp
28) Fenwick Tree (Binary Indexed Tree)

## A social network 100% devoted to making you a better coder?

### Join DEV Now

Open source

Free forever

Level up every day

Yes! 🤯

Discussion

Classic DEV Post from Jul 30 '19