# Ternary Search Trie(TST) with C++

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

``````class TrieNode {
public:
// 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){

}
~TrieNode(){
if(left)
delete left;
if(right)
delete right;
if(mid)
delete mid;
}
};

class Trie {
public:
Trie() {
root = NULL;
}
~Trie(){
delete root;
}

TrieNode *put(TrieNode *node, const string &str, int index){
if(!node){
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);
}else
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;
}

private:
TrieNode* root;
};``````

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

• @gdou2 sorry passing by value is certainly OK that way

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