Trie Search Operation in DSA Go

Mental Model

A trie stores words by branching letters step-by-step. Searching means following branches for each letter to see if the word exists.

Analogy: Imagine a tree where each branch is a letter. To find a word, you walk down the branches letter by letter until you reach the end of the word or get stuck.

root
 ↓
 a -> b -> c -> null
 ↓
 t (end)

Each arrow shows the next letter branch. 't (end)' means word ends here.

Dry Run Walkthrough

Input: Trie with words: "cat", "car", "bat"; search for "car"

Goal: Check if the word "car" exists in the trie

Step 1: Start at root node, look for branch 'c'

root -> [c] -> a -> t/null and r/null branches

Why: We must find the first letter 'c' to continue searching

Step 2: Move to node 'c', look for branch 'a'

root -> c -> [a] -> t/null and r/null branches

Why: Next letter 'a' must be found under 'c'

Step 3: Move to node 'a', look for branch 'r'

root -> c -> a -> [r] (end of word)

Why: Last letter 'r' must be found to confirm word

Step 4: Check if 'r' node marks end of word

root -> c -> a -> r (end)

Why: Only if this node marks end of word, 'car' exists

Result:

root -> c -> a -> r (end) confirms word "car" exists

Annotated Code

DSA Go

package main

import "fmt"

// TrieNode represents each node in the trie
type TrieNode struct {
	children map[rune]*TrieNode
	isEnd bool
}

// Trie structure with root node
type Trie struct {
	root *TrieNode
}

// NewTrieNode creates a new trie node
func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

// NewTrie creates a new trie
func NewTrie() *Trie {
	return &Trie{root: NewTrieNode()}
}

// Insert adds a word to the trie
func (t *Trie) Insert(word string) {
	curr := t.root
	for _, ch := range word {
		if curr.children[ch] == nil {
			curr.children[ch] = NewTrieNode() // create branch if missing
		}
		curr = curr.children[ch] // move to next node
	}
	curr.isEnd = true // mark end of word
}

// Search checks if a word exists in the trie
func (t *Trie) Search(word string) bool {
	curr := t.root
	for _, ch := range word {
		if curr.children[ch] == nil {
			return false // missing letter branch means word not found
		}
		curr = curr.children[ch] // move to next node
	}
	return curr.isEnd // true only if end of word
}

func main() {
	trie := NewTrie()
	trie.Insert("cat")
	trie.Insert("car")
	trie.Insert("bat")

	fmt.Println(trie.Search("car")) // true
	fmt.Println(trie.Search("cap")) // false
}

if curr.children[ch] == nil {

check if current letter branch exists

curr = curr.children[ch]

advance to next node along letter branch

return false

stop search early if letter branch missing

return curr.isEnd

confirm word exists only if last node marks end

Output

true

false

Complexity Analysis

Time: O(m) because we check each of the m letters in the word once

Space: O(1) for search since no extra space grows with input size

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster because it directly follows letter branches

Edge Cases

search empty string

returns false because no word is empty

DSA Go

return curr.isEnd // true only if end of word

search word not inserted

returns false when a letter branch is missing

DSA Go

if curr.children[ch] == nil { return false }

search prefix of a word but not a full word

returns false because isEnd is false at last node

DSA Go

return curr.isEnd

When to Use This Pattern

When you need to quickly check if words or prefixes exist in a set, use trie search because it follows letter branches step-by-step.

Common Mistakes

Mistake: Not checking if the last node marks the end of a word
Fix: Always check the isEnd flag after traversing all letters

Mistake: Returning true as soon as all letters are found without isEnd check
Fix: Return true only if the last node's isEnd is true

Summary

It checks if a word exists by following letter branches in the trie.

Use it when you want fast word lookups in a large dictionary.

The key is to follow each letter branch and confirm the word ends exactly there.