SimuVedaAlgorithms Lab Open in the lab

Trees / Advanced

Trie (Prefix Tree) Visualizer

Each edge is one letter. Words that share a prefix share the same path. A double ring marks where a full word ends.

Start the Trie (Prefix Tree) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(L)
Average timeO(L)
Worst timeO(L)
Extra spaceO(total letters)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Start with an empty root. Each step down the tree is one letter.
  2. "car": there is no "c" here yet, so create it.
  3. "car": there is no "a" here yet, so create it.
  4. "car": there is no "r" here yet, so create it.
  5. Mark where "car" ends (double ring).
  6. "cart": "c" already exists, so reuse it.
  7. "cart": "a" already exists, so reuse it.
  8. "cart": "r" already exists, so reuse it.
  9. "cart": there is no "t" here yet, so create it.
  10. Mark where "cart" ends (double ring).
  11. "care": "c" already exists, so reuse it.
  12. "care": "a" already exists, so reuse it.
  13. "care": "r" already exists, so reuse it.
  14. "care": there is no "e" here yet, so create it.
  15. Mark where "care" ends (double ring).
  16. "cat": "c" already exists, so reuse it.
  17. "cat": "a" already exists, so reuse it.
  18. "cat": there is no "t" here yet, so create it.
  19. Mark where "cat" ends (double ring).
  20. "dog": there is no "d" here yet, so create it.
  21. … 8 more steps …
  22. Follow "a".
  23. Follow "r".
  24. Follow "e".
  25. The path ends on a word marker. "care" is in the trie.

Try it with your own input →

Trie (prefix tree) in Java, Python, C++, C and JavaScript

void insert(String word) {
  TrieNode node = root;
  for (char c : word.toCharArray()) {
    if (!node.kids.containsKey(c))
      node.kids.put(c, new TrieNode());
    node = node.kids.get(c);
  }
  node.isEnd = true;
}
boolean search(String word) {
  TrieNode node = root;
  for (char c : word.toCharArray()) {
    node = node.kids.get(c);
    if (node == null) return false;
  }
  return node.isEnd;
}
class TrieNode:
    def __init__(self):
        self.kids, self.is_end = {}, False

def insert(root, word):
    node = root
    for c in word:
        if c not in node.kids:
            node.kids[c] = TrieNode()
        node = node.kids[c]
    node.is_end = True

def search(root, word):
    node = root
    for c in word:
        node = node.kids.get(c)
        if node is None:
            return False
    return node.is_end
struct TrieNode { unordered_map<char, TrieNode*> kids; bool isEnd = false; };

void insert(TrieNode* root, const string& word) {
  TrieNode* node = root;
  for (char c : word) {
    if (!node->kids.count(c))
      node->kids[c] = new TrieNode();
    node = node->kids[c];
  }
  node->isEnd = true;
}
bool search(TrieNode* root, const string& word) {
  TrieNode* node = root;
  for (char c : word) {
    auto it = node->kids.find(c);
    if (it == node->kids.end()) return false;
    node = it->second;
  }
  return node->isEnd;
}
#include <stdlib.h>

struct TrieNode { struct TrieNode* kids[26]; int isEnd; };

void insert(struct TrieNode* root, const char* word) {
  struct TrieNode* node = root;
  for (; *word; word++) {
    int c = *word - 'a';
    if (node->kids[c] == NULL)
      node->kids[c] = calloc(1, sizeof(struct TrieNode));
    node = node->kids[c];
  }
  node->isEnd = 1;
}
int search(struct TrieNode* root, const char* word) {
  struct TrieNode* node = root;
  for (; *word; word++) {
    node = node->kids[*word - 'a'];
    if (node == NULL) return 0;
  }
  return node->isEnd;
}
function insert(root, word) {
  let node = root;
  for (const c of word) {
    if (!node.kids.has(c))
      node.kids.set(c, { kids: new Map(), isEnd: false });
    node = node.kids.get(c);
  }
  node.isEnd = true;
}
function search(root, word) {
  let node = root;
  for (const c of word) {
    node = node.kids.get(c);
    if (node === undefined) return false;
  }
  return node.isEnd;
}

In an interview

LeetCode 208, Implement Trie. Also used in 211 (word search with dots) and 212 (Word Search II).

Search for "ca" in the example: the path exists but no word ends there. That difference between search and startsWith is a common follow-up.

More trees