Longest Word in Dictionary Using Trie in DSA Go

Mental Model

Build a tree where each path is a word, then find the longest word where every prefix is also a word.

Analogy: Imagine a family tree where each generation must be complete before moving to the next; the longest name is the deepest complete branch.

root
 ↓
 t -> r -> i -> e
 ↑
 start

Dry Run Walkthrough

Input: words: ["a", "ap", "app", "appl", "apple", "apply"]

Goal: Find the longest word where all prefixes are also words in the list

Step 1: Insert 'a' into trie

root -> a[isWord=true]

Why: Start building trie with first word

Step 2: Insert 'ap' into trie

root -> a[isWord=true] -> p[isWord=true]

Why: Add second word, marking prefix 'ap' as word

Step 3: Insert 'app' into trie

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true]

Why: Add third word, all prefixes so far are words

Step 4: Insert 'appl' into trie

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> l[isWord=true]

Why: Add fourth word, prefix 'appl' is word

Step 5: Insert 'apple' into trie

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> l[isWord=true] -> e[isWord=true]

Why: Add fifth word, all prefixes valid

Step 6: Insert 'apply' into trie

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> l[isWord=true] -> y[isWord=true]

Why: Add sixth word, all prefixes valid

Step 7: Search longest word with all prefixes as words

Check words: 'a', 'ap', 'app', 'appl', 'apple', 'apply'

Why: Find longest valid word

Step 8: Choose 'apple' as longest valid word (lex smaller than 'apply')

Result: 'apple'

Why: Both 'apple' and 'apply' valid, choose lex smaller

Result:

apple

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type TrieNode struct {
	children map[rune]*TrieNode
	isWord   bool
}

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
	curr := t.root
	for _, ch := range word {
		if curr.children[ch] == nil {
			curr.children[ch] = NewTrieNode()
		}
		curr = curr.children[ch]
	}
	curr.isWord = true
}

func (t *Trie) LongestWord() string {
	var result string
	var dfs func(node *TrieNode, path []rune)
	dfs = func(node *TrieNode, path []rune) {
		if node != t.root && !node.isWord {
			return
		}
		if len(path) > len(result) || (len(path) == len(result) && string(path) < result) {
			result = string(path)
		}
		for ch := 'a'; ch <= 'z'; ch++ {
			if node.children[ch] != nil {
				dfs(node.children[ch], append(path, ch))
			}
		}
	}
	dfs(t.root, []rune{})
	return result
}

func main() {
	words := []string{"a", "ap", "app", "appl", "apple", "apply"}
	trie := NewTrie()
	for _, w := range words {
		trie.Insert(w)
	}
	fmt.Println(trie.LongestWord())
}

for _, ch := range word { if curr.children[ch] == nil { curr.children[ch] = NewTrieNode() } curr = curr.children[ch] }

Insert each character, creating nodes if missing, advancing current pointer

curr.isWord = true

Mark end of inserted word as valid word

if node != t.root && !node.isWord { return }

Stop DFS if current node is not a word (prefix missing)

if len(path) > len(result) || (len(path) == len(result) && string(path) < result) { result = string(path) }

Update result if current path is longer or lex smaller when equal length

for ch := 'a'; ch <= 'z'; ch++ { if node.children[ch] != nil { dfs(node.children[ch], append(path, ch)) } }

DFS children in alphabetical order to ensure lex order

Output

apple

Complexity Analysis

Time: O(N * L) because we insert N words each of length L and DFS visits nodes once

Space: O(N * L) for trie nodes storing all characters of all words

vs Alternative: Compared to sorting and checking prefixes in array (O(N log N * L)), trie offers efficient prefix checks

Edge Cases

Empty word list

Returns empty string as no words exist

DSA Go

if node != t.root && !node.isWord { return }

Words with no valid prefixes except single letters

Returns shortest valid word with all prefixes present

DSA Go

if node != t.root && !node.isWord { return }

Multiple longest words with same length

Returns lexicographically smallest word

DSA Go

if len(path) > len(result) || (len(path) == len(result) && string(path) < result) { result = string(path) }

When to Use This Pattern

When asked to find the longest word with all prefixes present, use a trie to efficiently check prefixes and find the answer by DFS.

Common Mistakes

Mistake: Not checking if all prefixes are words before updating result
Fix: Add condition to stop DFS if current node is not marked as word

Mistake: Not exploring children in alphabetical order causing wrong lexicographical result
Fix: Traverse children from 'a' to 'z' to ensure lex order

Summary

Build a trie from words and find the longest word where every prefix is also a word.

Use when you need to find words with all prefixes present efficiently.

The key is to stop exploring paths where prefixes are missing and to explore children in alphabetical order.