Memory efficient Trie Implementation in C++ using Map | Insert, Search and Delete

In this post, we will cover memory efficient Trie implementation in C++ using map data structure.


Trie is a tree-based data structure, which is used for efficient retrieval of a key in a large data-set of strings.

There are several ways to represent tries, corresponding to different trade-offs between memory use and speed of the operations. The basic form is that of a linked set of nodes, where each node contains an array of child pointers, one for each symbol in the alphabet (so for the English alphabet, one would store 26 child pointers and for the alphabet of bytes, 256 pointers).

This is simple but wasteful in terms of memory: using the alphabet of bytes (size 256) and four-byte pointers, each trie node requires a kilobyte of storage, and when there is little overlap in the strings’ prefixes, the number of required nodes is roughly the combined length of the stored strings. Also, the nodes near the bottom of the tree tend to have few children and there are many of them, so the structure wastes space storing null pointers.

The storage problem can be alleviated by an implementation where we use map to store children of a node. Now we allocate memory only for alphabets in use, and don’t waste space storing null pointers.

C++ implementation –

Download   Run Code


1 1 0 1 1
0 1 1
0 1 1
0 1 0
Trie empty!!


Also see: Java Implementation of Trie Data Structure


1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

Nice implementation. Keep up the good work!!


and it’s not space efficient if you really think about millions of string insertion, check this solution for an english directory having as less as 400K words and check it’s space efficiency.

Tom K.

Also take a look at Judy arrays which are more efficient.


Hi Techie Delight, I loved your post but since I am java user I tried implementing it in java, I am not able to delete the node, I would be glad if you can help me asap.


I dont see how the use of a map, which is literally an array with a hash function, is a better than the use of a known bounded array (the underlying structure for the map might be actually bigger than the ascii table length).

Why not using a ternary tree instead ?