Beyond Basic Trie: Exploring DFS, Backtracking, and Prefix-Based Searching

Trie is one of those data structures that becomes much more interesting when we move beyond simple word insertion and searching.

Initially, we use Trie to store words character by character. But when we combine Trie with DFS (Depth First Search), we can solve more complex problems involving word searching, prefix matching, and dictionary-based operations.

Recently, I solved three interesting LeetCode problems:

• LC 212 — Word Search II
• LC 648 — Replace Words
• LC 677 — Map Sum Pairs

All three use Trie, but each demonstrates a different application of the data structure.

Before understanding these problems, let’s first understand DFS in Trie.

1. Understanding DFS in Trie

What is DFS?

DFS stands for Depth First Search.

It is a traversal technique in which we explore one path as deeply as possible before coming back and exploring another path.

Real-life analogy: Exploring a building

Imagine entering a building with multiple floors and rooms.

You enter the first room, explore everything inside it, and if another room is available, you enter that room.

You continue exploring until you cannot go further. Then you return to the previous room and explore another available path.

This is exactly how DFS works.

How does DFS work in Trie?

Consider the following words:

• APP
• APPLE
• APPLY
• BAT

Their Trie structure looks like this:

             root
            /    \
           A      B
           |      |
           P      A
           |      |
           P      T*
          / \
         L*  L
         |   |
         E*  Y*

* represents the end of a complete word.

Now consider searching for all words starting with APP.

DFS explores the Trie like this:

root
  |
  A
  |
  P
  |
  P*
 / \
L   L
|   |
E*  Y*

The traversal explores:

1. A → P → P
2. Checks whether APP is a complete word.
3. Moves towards L → E and finds APPLE.
4. Backtracks to the previous node.
5. Explores L → Y and finds APPLY.

This process is called DFS traversal in Trie.

Basic DFS implementation

void dfs(Node* root, string& word) {

    if (root->isEnd) {
        cout << word << endl;
    }
    for (int i = 0; i < 26; i++) {
        if (root->children[i] != NULL) {
            word.push_back('a' + i);
            dfs(root->children[i], word);
            word.pop_back();
        }
    }
}

Important concepts:

• dfs() explores one branch completely.
• push_back() adds the current character.
• Recursive calls move deeper into the Trie.
• pop_back() removes the last character while backtracking.
• isEnd identifies whether the current path represents a complete word.

Remember: DFS explores paths, while Trie stores the prefix structure. Combining them allows us to explore multiple words efficiently.

2. LC 212 — Word Search II

Problem: https://leetcode.com/problems/word-search-ii/

Problem Understanding

We are given:

• A 2D character board.
• A list of words.

Our task is to find all words that can be formed by connecting adjacent cells.

We can move in four directions:

• Up
• Down
• Left
• Right

We cannot use the same cell more than once while forming a single word.

Real-Life Analogy: Finding Words in a Word Puzzle

Imagine a newspaper puzzle containing letters arranged in a grid.

You are given a dictionary containing hundreds of words.

Your task is to find every dictionary word hidden inside the grid.

Instead of checking each word independently, imagine having a dictionary organized as a Trie.

Whenever you move through the grid, you follow the corresponding Trie path.

If the next character does not exist in the Trie, there is no reason to continue exploring that path.

This is where Trie + DFS becomes powerful.

Example

Input:

board = {
    {'o','a','a','n'},
    {'e','t','a','e'},
    {'i','h','k','r'},
    {'i','f','l','v'}
};

words = {"oath", "pea", "eat", "rain"};

Output:

["eat", "oath"]

How Trie + DFS Works

Step 1: Build the Trie

Insert all dictionary words into Trie.

root
 ├── o
 │   └── a
 │       └── t
 │           └── h*
 ├── p
 │   └── e
 │       └── a*
 ├── e
 │   └── a
 │       └── t*
 └── r
     └── a
         └── i
             └── n*

Step 2: Start DFS from every board cell

For every cell:

1. Check whether its character exists in the Trie.
2. If it doesn’t exist, stop exploring that path.
3. If it exists, move to the corresponding Trie node.
4. Explore all four neighboring cells.
5. If a complete word is found, add it to the answer.

Step 3: Apply Backtracking

After exploring a cell, mark it as unvisited again so that another path can use it.

For example, when searching for OATH:

O → A → T → H

DFS follows this path and finds the complete word.

Similarly, another DFS path discovers EAT.

Important optimization:

After finding a word, we can clear its terminal marker in the Trie to avoid adding the same word multiple times.

We also prune branches that no longer contain any valid words.

Complexity Analysis

Let:

• M = number of board rows.
• N = number of board columns.
• L = maximum word length.
• S = total number of characters across all dictionary words.

Time Complexity:

• Trie construction: O(S)
• DFS search: O(M × N × 4 × 3^(L-1)) in the worst case.

Space Complexity:

• Trie: O(S)
• DFS recursion: O(L)

The Trie allows us to stop exploring paths that cannot form any dictionary word.

3. LC 648 — Replace Words

Problem: https://leetcode.com/problems/replace-words/

Problem Understanding

We are given:

• A dictionary containing root words.
• A sentence containing multiple words.

We need to replace every word with the shortest root that is its prefix.

Get Harsh Jaiswal’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

If no root matches a word, we keep the original word.

Real-Life Analogy: Dictionary Autocomplete

Imagine a dictionary containing these root words:

cat
bat
rat

Now someone types:

cattle
battery
rattling

The dictionary recognizes that:

• cattle starts with cat.
• battery starts with bat.
• rattling starts with rat.

Instead of keeping the complete words, we replace them with their shortest matching roots.

This is similar to an autocomplete system that recognizes prefixes.

Example

Input:

dictionary = {"cat", "bat", "rat"};

sentence = "the cattle was rattled by the battery";

Output:

the cat was rat by the bat

How Trie Works Here

Step 1: Insert dictionary roots into Trie

root
 ├── c → a → t*
 ├── b → a → t*
 └── r → a → t*

Step 2: Process each sentence word

Consider the word:

cattle

Start from the root of Trie.

• Read c → character exists.
• Read a → character exists.
• Read t → terminal node found.

We have found the shortest root: cat.

There is no need to process the remaining characters tle.

Similarly:

battery → bat
rattled  → rat

Step 3: Handle words without a matching root

If the Trie traversal fails before reaching a terminal node, keep the original word.

For example:

was → was
the → the

Why is the shortest prefix important?

Suppose the dictionary contains:

cat
cattle

And the sentence contains:

cattle

The answer must be:

cat

As soon as we reach a terminal node, we return the root instead of continuing further.

This is one of the most important properties of this problem.

Complexity Analysis

Let:

• D = total characters in the dictionary.
• T = total characters in the sentence.

Time Complexity: O(D + T)

• Building Trie takes O(D).
• Processing all sentence characters takes O(T).

Space Complexity: O(D)

The Trie stores all dictionary prefixes and their character connections.

4. LC 677 — Map Sum Pairs

Problem: https://leetcode.com/problems/map-sum-pairs/

Problem Understanding

We need to design a MapSum class with two operations:

1. insert(key, val) — Insert a key with its corresponding value.
2. sum(prefix) — Return the sum of values of all keys starting with the given prefix.

If an existing key is inserted again, its old value must be replaced.

Real-Life Analogy: Sales Tracking by Category

Imagine an online shopping platform.

Every product has:

• A product name.
• A sales value.

Example

Operations:

insert("apple", 3);
sum("ap");
insert("app", 2);
sum("ap");

Output:

0
5

Let’s understand why.

How Trie Works Here

Step 1: Insert apple with value 3

As we traverse:

root → a → p → p → l → e

We add 3 to the sum of every node along this path.

root
  |
 a(3)
  |
 p(3)
  |
 p(3)
  |
 l(3)
  |
 e(3)

Step 2: Calculate sum(“ap”)

We traverse:

root → a → p

The sum stored at the p node is 3.

Therefore:

sum("ap") = 3;

Step 3: Insert app with value 2

Now we traverse:

root → a → p → p

Add 2 to the existing sums.

root
  |
 a(5)
  |
 p(5)
  |
 p(5)
 / 
l(3)
 |
e(3)

Now the prefix ap has a total value of 5.

Therefore:

sum("ap") = 5;

Important Concept: Updating Existing Keys

What happens if we insert the same key again?

insert("apple", 3);
insert("apple", 5);

The answer should not become 8.

It should become 5 because the old value is replaced.

To handle this, we maintain the previous value of each key.

We calculate:

delta = newValue - oldValue;

Then update every Trie node along that key’s path using this delta.

For example:

oldValue = 3;
newValue = 5;

delta = 5 - 3 = 2;

Every node along apple receives an additional 2.

This ensures that the prefix sums remain correct.

Complexity Analysis

Let K be the length of the key or prefix.

Time Complexity:

• insert(): O(K)
• sum(): O(K)

Space Complexity: O(S), where S is the total number of characters stored in the Trie, plus the auxiliary key-value records.

The main advantage is that each prefix sum is directly available at its corresponding Trie node.

Final Takeaways

1. Trie + DFS: Useful when we need to explore multiple possible paths and find valid words.
2. Trie + Prefix Matching: Useful when we need to find the shortest or longest matching prefix.
3. Trie + Node Values: Useful when we need to store additional information at each prefix node.

Trie is not limited to storing strings. We can also attach additional information to its nodes and use recursion, DFS, and backtracking to solve more advanced problems.

👋 Connect with Me:
🔎LEETCODE :- https://leetcode.com/u/HARSHJAISWAL2707/

👤LinkedIn :- https://www.linkedin.com/in/mr-harsh-jaiswal-76691a32a/

Written by Mr. Harsh Jaiswal — B.Tech CSE | DSA & Web Development

#DFS #Prefix #Tries #DSA #CodingInterview #EnjoyProblems