Ternary Search Trie(TST) with C++

  • 0

    although the time complexity is O(lg(n)), it would save some space

    class TrieNode {
    // Initialize your data structure here.
    bool is_end;
    /* T-ST implemention */
    TrieNode *left, *mid, *right;
    char c;
    TrieNode(char _c):c(_c),left(NULL),mid(NULL),right(NULL),is_end(false){
            delete left;
            delete right;
            delete mid;
    class Trie {
        Trie() {
            root = NULL;
            delete root;
    TrieNode *put(TrieNode *node, const string &str, int index){
            node = new TrieNode(str[index]);
        if(node->c > str[index])
            node->left = put(node->left, str, index);
        else if(node->c < str[index])
            node->right = put(node->right, str, index);
        else if(index < str.size()-1){
            node->mid = put(node->mid, str, index+1);
            node->is_end = true;
        return node;
    // Inserts a word into the trie.
    void insert(string word) {
        root = put(root, word, 0);
    // Returns if the word is in the trie.
    TrieNode *get(TrieNode *node, const string &str, int index){
        if(node == NULL)
            return NULL;
        if(node->c > str[index])
            return get(node->left, str, index);
        if(node->c < str[index])
            return get(node->right, str, index);
        if(index < str.size()-1)
            return get(node->mid, str, index+1);
        return node;
    bool search(string word) {
        TrieNode *p = get(root, word, 0);
        return p&&p->is_end;
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *p = get(root, prefix, 0);
        return p!=NULL;
        TrieNode* root;

  • 0

    @mzeric should pass node by reference in put method...right?

  • 0

    @gdou2 sorry passing by value is certainly OK that way

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.