# How to implement trie in C++

📅 2015-Nov-02 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ cpp, trie ⬩ 📚 Archive

Trie, also known as prefix tree, is an elegant and efficient data structure to use as a symbol table for keys that are strings. In a trie, the number of accesses required to search or insert a string is linear in the string length. In fact, it is just one more than the number of characters in the string.

Sedgewick's Algorithms textbook has a particularly elegant trie implementation in Java. I created a similar C++ version just for fun here:

``````// Adapted from Trie code in Algorithms (4 Ed) by Sedgewick

#include <iostream>
#include <string>

// Size of alphabet
constexpr int R = 256;

struct Node
{
Node*       next_[R] = {};
std::string val_;
};

class Trie
{
public:

void Put(const std::string& key, const std::string& val)
{
root_ = Put(root_, key, val, 0);
}

std::string Get(const std::string& key)
{
Node* x = Get(root_, key, 0);

if (!x)
return "";

return x->val_;
}

private:

Node* Put(Node* x, const std::string& key, const std::string& val, int d)
{
if (!x)
x = new Node();

if (d == key.size())
{
x->val_ = val;
return x;
}

char c      = key.at(d);
x->next_[c] = Put(x->next_[c], key, val, d + 1);

return x;
}

Node* Get(Node* x, const std::string& key, int d)
{
if (!x)
return nullptr;

if (d == key.size())
return x;

char c = key.at(d);

return Get(x->next_[c], key, d + 1);
}

Node* root_ {};
};

int main()
{
Trie t;
t.Put("cat", "feline animal");
t.Put("rat", "eaten by cat");

std::cout << t.Get("rat") << std::endl;
std::cout << t.Get("cow") << std::endl;

t.Put("rat", "a rodent");

std::cout << t.Get("rat") << std::endl;

return 0;
}``````