children is a hash map to store the alphabets which leads to new nodes
endOfWord inndicates whether a word ends at the particular node

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()  # Fixed: added () to instantiate
            cur = cur.children[c]
        cur.endOfWord = True

    def delete(self, word):
        def dfs(node, i):
            # Reached the node representing the complete word
            if i == len(word):
                if not node.endOfWord:
                    return False, False  # word doesn't exist
                node.endOfWord = False
                # Parent can delete this node if it has no children
                return True, len(node.children) == 0

            if word[i] not in node.children:
                return False, False

            child = node.children[word[i]]
            deleted, shouldDeleteChild = dfs(child, i + 1)

            if not deleted:
                return False, False

            # Child has become useless → remove it
            if shouldDeleteChild:
                node.children.pop(word[i])

            # Current node can now also be pruned
            return True, len(node.children) == 0 and not node.endOfWord

        dfs(self.root, 0)

    def search(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.endOfWord

    def startsWith(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

Trie — Implementation

Tags: #DSA #Trie #Tree #String #PrefixTree #DataStructures #Insert #Search #Delete #Recursion

1. What is a Trie?

A Trie (Prefix Tree) is a tree-like data structure used to store strings where:

Each edge represents a character.
A path from the root represents a string/prefix.
endOfWord = True marks that a complete word ends at that node.
children stores the next possible characters.

Example

Insert:

cat
car
cart

The Trie becomes conceptually:

root
 └── c
      └── a
           ├── t [EOW]
           └── r [EOW]
                └── t [EOW]

[EOW] means endOfWord = True.

Notice that car and cart share the path:

c → a → r

This is the main advantage of a Trie: common prefixes are shared.

2. Node Structure

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

Every Trie node contains two pieces of information.

`children`

self.children = {}

A dictionary mapping:

character → TrieNode

For example:

{
    'a': TrieNode,
    'b': TrieNode
}

means that from the current node we can move to either a or b.

Using a dictionary also means we can check whether a character exists in approximately $O(1)$ average time.

`endOfWord`

self.endOfWord = False

This tells us whether the current node represents the end of a complete inserted word.

This distinction is important.

Suppose we insert:

car
cart

The node representing r has:

endOfWord = True

because "car" is a complete word.

It also has a child:

r → t

because "cart" exists.

Therefore, a node can simultaneously be the end of one word and a prefix of another word.

3. Trie Initialization

class Trie:
    def __init__(self):
        self.root = TrieNode()

The Trie always starts with an empty root node.

root

The root does not represent a character.

It simply acts as the starting point for every word.

4. Insert

def insert(self, word):
    cur = self.root

    for c in word:
        if c not in cur.children:
            cur.children[c] = TrieNode()

        cur = cur.children[c]

    cur.endOfWord = True

Idea

For every character:

Check whether the current node already has that character as a child.
If not, create a new node.
Move cur to that child.
After processing the entire word, mark the final node as endOfWord.

Example: Insert `"cat"`

Initially:

root

Process `'c'`

c does not exist:

if 'c' not in cur.children:
    cur.children['c'] = TrieNode()

Now:

root
 └── c

Move:

cur = cur.children['c']

Process `'a'`

Create a:

root
 └── c
      └── a

Process `'t'`

Create t:

root
 └── c
      └── a
           └── t

After the loop:

cur.endOfWord = True

Therefore:

root
 └── c
      └── a
           └── t [EOW]

Now "cat" exists in the Trie.

Inserting a word with an existing prefix

Suppose "cat" already exists and we insert:

car

We already have:

c → a

so we reuse those nodes.

Only r needs to be created:

root
 └── c
      └── a
           ├── t [EOW]
           └── r [EOW]

This is the prefix sharing property of a Trie.

5. Search

def search(self, word):
    cur = self.root

    for c in word:
        if c not in cur.children:
            return False

        cur = cur.children[c]

    return cur.endOfWord

Important idea

Searching has two conditions:

The entire character path must exist.
The final node must have endOfWord = True.

The second condition is essential.

Example

Suppose the Trie contains:

car

Then:

root
 └── c
      └── a
           └── r [EOW]

Search `"car"`

We successfully follow:

c → a → r

At r:

cur.endOfWord == True

Therefore:

search("car") → True

Search `"ca"`

We successfully follow:

c → a

But:

a.endOfWord == False

Therefore:

search("ca") → False

Even though "ca" is a valid prefix, it was not inserted as a complete word.

Key distinction

Path exists ≠ Word exists

A path represents a prefix.

endOfWord = True tells us that the prefix is also a complete word.

6. Starts With / Prefix Search

def startsWith(self, word):
    cur = self.root

    for c in word:
        if c not in cur.children:
            return False

        cur = cur.children[c]

    return True

Unlike search(), we do not check endOfWord.

We only care whether the entire prefix path exists.

Example

Trie contains:

car
cart
cat

Conceptually:

root
 └── c
      └── a
           ├── r [EOW]
           │    └── t [EOW]
           │
           └── t [EOW]

`startsWith("ca")`

Path exists:

c → a

Therefore:

True

even though "ca" itself isn’t necessarily a word.

`startsWith("car")`

Path exists:

c → a → r

Therefore:

True

`startsWith("cab")`

There is no b after ca.

Therefore:

False

7. Delete

Deletion is the most interesting operation because simply removing the characters can break other words that share the same prefix.

Our implementation uses DFS + backtracking.

def delete(self, word):
    def dfs(node, i):
        if i == len(word):
            if not node.endOfWord:
                return False, False

            node.endOfWord = False

            return True, len(node.children) == 0

        if word[i] not in node.children:
            return False, False

        child = node.children[word[i]]

        deleted, shouldDeleteChild = dfs(child, i + 1)

        if not deleted:
            return False, False

        if shouldDeleteChild:
            node.children.pop(word[i])

        return True, len(node.children) == 0 and not node.endOfWord

    dfs(self.root, 0)

8. Why Can’t We Simply Remove the Word?

Suppose the Trie contains:

car
cart

root
 └── c
      └── a
           └── r [EOW]
                └── t [EOW]

If we delete "cart", we should get:

root
 └── c
      └── a
           └── r [EOW]

We only remove t.

But if we delete "car":

root
 └── c
      └── a
           └── r [EOW]
                └── t [EOW]

we must not remove r, because cart still needs it.

Therefore deletion must determine:

“After deleting this word, is this node still needed?”

9. The Two Return Values of DFS

Our DFS returns:

(deleted, shouldDelete)

These mean two different things.

`deleted`

Was the requested word actually found and deleted?

`shouldDelete`

Can this node now be removed by its parent?

So:

(deleted, shouldDelete)

is essentially:

(word was deleted?, this node can be pruned?)

This allows information to propagate from the bottom of the Trie back toward the root.

10. Delete Example — `"cart"`

Consider:

car
cart

Trie:

root
 └── c
      └── a
           └── r [EOW]
                └── t [EOW]

We call:

delete("cart")

DFS travels downward:

root
  ↓
 c
  ↓
 a
  ↓
 r
  ↓
 t

At t:

i == len(word)

We have reached the node representing "cart".

Since:

t.endOfWord == True

we execute:

t.endOfWord = False

Now:

t
endOfWord = False
children = {}

Therefore:

return True, True

Meaning:

True  → "cart" was deleted.
True  → t can be deleted.

11. Returning to the Parent

We return to r.

We received:

deleted = True
shouldDeleteChild = True

Therefore:

if shouldDeleteChild:
    node.children.pop('t')

So:

no longer has a t child.

Now r looks like:

r
├── endOfWord = True
└── children = {}

Can r be deleted?

No.

Because:

not node.endOfWord

is False.

Therefore:

return True, False

Meaning:

"cart" was deleted,
but r must remain because "car" still exists.

The final Trie is:

root
 └── c
      └── a
           └── r [EOW]

12. Delete Example — `"car"`

Now suppose the Trie contains:

car

only:

root
 └── c
      └── a
           └── r [EOW]

Call:

delete("car")

DFS reaches r.

At the terminal node:

r.endOfWord = False

Now:

r
├── endOfWord = False
└── children = {}

Therefore:

return True, True

r can be deleted.

Backtracking

Parent a receives:

(True, True)

so:

a.children.pop('r')

Now a has no children and is not the end of a word.

Therefore:

return True, True

The same thing happens for c.

Eventually:

root

has no children.

The entire path has been pruned.

13. Why `not node.endOfWord` Matters

This condition:

return True, len(node.children) == 0 and not node.endOfWord

is critical.

Consider:

car
cart

After deleting "cart":

r
├── endOfWord = True
└── children = {}

Although:

len(r.children) == 0

we cannot delete r.

Why?

Because r represents the word "car".

Therefore:

len(node.children) == 0

alone is insufficient.

We need:

len(node.children) == 0 and not node.endOfWord

Meaning:

“This node has no children AND does not represent the end of another word.”

Only then is the node completely useless.

14. Delete a Non-existent Word

Suppose Trie contains:

cat

and we call:

delete("car")

DFS follows:

c → a

At a, we look for:

but only:

exists.

Therefore:

if word[i] not in node.children:
    return False, False

This propagates:

False, False

all the way back to the root.

Nothing is modified.

15. Complete Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False


class Trie:

    def __init__(self):
        self.root = TrieNode()


    def insert(self, word):
        cur = self.root

        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()

            cur = cur.children[c]

        cur.endOfWord = True


    def delete(self, word):

        def dfs(node, i):

            # Reached the node representing the complete word
            if i == len(word):

                if not node.endOfWord:
                    return False, False

                node.endOfWord = False

                # Parent can delete this node if it has no children
                return True, len(node.children) == 0


            if word[i] not in node.children:
                return False, False


            child = node.children[word[i]]

            deleted, shouldDeleteChild = dfs(child, i + 1)


            if not deleted:
                return False, False


            # Child became useless → remove it
            if shouldDeleteChild:
                node.children.pop(word[i])


            # Current node can now also be pruned
            return True, len(node.children) == 0 and not node.endOfWord


        dfs(self.root, 0)


    def search(self, word):

        cur = self.root

        for c in word:

            if c not in cur.children:
                return False

            cur = cur.children[c]

        return cur.endOfWord


    def startsWith(self, word):

        cur = self.root

        for c in word:

            if c not in cur.children:
                return False

            cur = cur.children[c]

        return True

16. Complexity

Let $L$ be the length of the word/prefix.

Operation	Time	Auxiliary Space
`insert`	$O(L)$	$O(1)$
`search`	$O(L)$	$O(1)$
`startsWith`	$O(L)$	$O(1)$
`delete`	$O(L)$	$O(L)$

Why is deletion space $O(L)$ ?

Deletion uses recursive DFS:

root
 ↓
 c
 ↓
 a
 ↓
 r
 ↓
 t

There can be at most $L$ recursive calls.

Therefore recursion stack:

O(L)O(L)

The Trie nodes themselves are not counted as auxiliary space because they are the existing data structure.

17. Core Invariants to Remember

Insert

Every character corresponds to a node along the path.
Final node → endOfWord = True

Search

Entire path must exist
AND
final node must have endOfWord = True

StartsWith

Entire prefix path must exist.
endOfWord does not matter.

Delete

A node can be pruned only when:

No children
AND
Not endOfWord

The recursive deletion communicates:

(deleted, shouldDelete)

where:

deleted
    ↓
Was the requested word successfully deleted?

shouldDelete
    ↓
Can the parent safely remove this node?

18. Mental Model for Trie Deletion

The easiest way to remember the deletion algorithm is:

Go down to the end of the word, unmark it, then walk back upward pruning nodes that have become useless.

At every node during the return:

Did deletion succeed?
        │
        ├── No → stop; nothing to modify
        │
        └── Yes
              │
              ├── Child useless? → remove child
              │
              └── Am I useless?
                    │
                    ├── no children
                    └── not endOfWord

This is essentially post-order processing of the word’s Trie path:

Go down:
root → c → a → r → t

Come back:
t → r → a → c → root

The downward phase finds the word.

The upward phase performs pruning.

Trie — Implementation

1. What is a Trie?

Example

2. Node Structure

children

endOfWord

3. Trie Initialization

4. Insert

Idea

Example: Insert "cat"

Process 'c'

Process 'a'

Process 't'

Inserting a word with an existing prefix

5. Search

Important idea

Example

Search "car"

Search "ca"

Key distinction

6. Starts With / Prefix Search

Example

startsWith("ca")

startsWith("car")

startsWith("cab")

7. Delete

8. Why Can’t We Simply Remove the Word?

9. The Two Return Values of DFS

deleted

shouldDelete

10. Delete Example — "cart"

11. Returning to the Parent

12. Delete Example — "car"

Backtracking

13. Why not node.endOfWord Matters

14. Delete a Non-existent Word

15. Complete Implementation

16. Complexity

Why is deletion space O(L)O(L)O(L)?

17. Core Invariants to Remember

Insert

Search

StartsWith

Delete

18. Mental Model for Trie Deletion

Local Graph View

`children`

`endOfWord`

Example: Insert `"cat"`

Process `'c'`

Process `'a'`

Process `'t'`

Search `"car"`

Search `"ca"`

`startsWith("ca")`

`startsWith("car")`

`startsWith("cab")`

`deleted`

`shouldDelete`

10. Delete Example — `"cart"`

12. Delete Example — `"car"`

13. Why `not node.endOfWord` Matters

Why is deletion space $O(L)$ ?