Trees
Building your tree…
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
Trees
Building your tree…
Each path from root to an end-of-word node spells a complete word. Shared prefixes share edges — making prefix queries and autocomplete O(L).
Words in set: code, coder, coding, cup, cat — select a word above to see its insertion
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return TrueWhat is the time complexity of inserting a word of length L into a Trie?
1/3