.. include:: ../global.rst

.. index::
    pair: C++; Stacks and Queues

Tries and Adapting Data Structures
===================================
- A Trie (pronounced “try”) is a tree-like data structure used to efficiently store and search strings (like words). It’s sometimes called a prefix tree, because it stores data based on common prefixes.
- Each node represents a character, and a path from the root to a node spells out a prefix of some word.
- Uses partitions of strings.
- Was originally used to help search when computer were dumb back in the day.
-  “Adapting” data structures means tweaking or combining them to better fit your problem.

.. code-block:: cpp

    #include <iostream>
    #include <unordered_map>
    using namespace std;

    struct TrieNode {
        bool isEnd;
        unordered_map<char, TrieNode*> children;

        TrieNode() : isEnd(false) {}
    };

    class Trie {
    private:
        TrieNode* root;

    public:
        Trie() { root = new TrieNode(); }

        void insert(const string &word) {
            TrieNode* node = root;
            for (char ch : word) {
                if (!node->children[ch])
                    node->children[ch] = new TrieNode();
                node = node->children[ch];
            }
            node->isEnd = true;
        }

        bool search(const string &word) {
            TrieNode* node = root;
            for (char ch : word) {
                if (!node->children.count(ch))
                    return false;
                node = node->children[ch];
            }
            return node->isEnd;
        }

        bool startsWith(const string &prefix) {
            TrieNode* node = root;
            for (char ch : prefix) {
                if (!node->children.count(ch))
                    return false;
                node = node->children[ch];
            }
            return true;
        }
    };

    int main() {
        Trie trie;
        trie.insert("cat");
        trie.insert("car");

        cout << trie.search("cat") << endl;      // 1 (true)
        cout << trie.search("cap") << endl;      // 0 (false)
        cout << trie.startsWith("ca") << endl;   // 1 (true)
    }

.. _tries: