Skip to content
Tutorials Center
My learning

Topics

Lesson 113 of 225 ยท Tries and Range Queries

Trie Applications

Put tries to work in Python: autocomplete with top-k, longest common prefix, Word Search II, maximum XOR pair with a bitwise trie and compressed radix trees.

In Tries you built the basic structure: insert, search and prefix walk. Now we use it. A trie is rarely the final answer by itself; it is the fast index underneath bigger problems. This lesson covers five classic uses: autocomplete that ranks suggestions, the longest common prefix, pruning a board search (Word Search II), a binary trie that finds the maximum XOR of two numbers, and the compressed trie (radix tree) that saves memory.

All examples reuse the same small building block: a node with a dictionary of children.

1. Autocomplete with ranking

A search box wants the top k most popular completions of what you typed. Store a popularity count at each word's end node. To answer a query, walk to the prefix node, collect all words below it, and keep the k best.

Brute force: scan every word and check startswith. That is O(N ร— L) per query. The trie jumps straight to the prefix in O(L), then only visits matching words. For choosing the best k from M matches, heapq.nsmallest(k, ...) runs in O(M log k) (see Top-K Problems).

Python Autocomplete with top-k suggestions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a very busy system you can store the top-k list inside each node while inserting. Queries then take O(L) with no subtree walk, at the cost of more memory and slower updates.

2. Longest common prefix

Given many strings, find the longest prefix they all share. Insert them all, then walk from the root while the current node has exactly one child and is not the end of a word. Where the path forks (or a word ends) the common part is over.

TEXT
words: flower, flow, flight

root -> f -> l -> (o | i)      fork after "fl"      answer: "fl"

For this single question, comparing the words character by character is simpler (O(total characters), no extra memory). The trie wins when you ask the question repeatedly for different subsets or add words over time.

Python Longest common prefix: trie vs direct comparison

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

3. Word Search II: pruning with a trie

You get a grid of letters and a list of words. Find every word that can be built by walking to adjacent cells (up, down, left, right) without reusing a cell in the same word.

Brute force: for each word, run a backtracking search over the board. With W words of length L on an Rร—C board, that is roughly W ร— R ร— C ร— 3^L steps. Many words repeat the same starting letters, so the same paths are explored again and again.

Better: put all words into a trie and run one backtracking search over the board, following trie edges as you walk. At each cell, you only continue if the current path is a prefix of some word. This shares the work among words with a common prefix and prunes dead paths immediately.

Python Word Search II with a trie

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trie-pruned search also lets you delete a leaf after finding its word, so later paths stop exploring used-up branches. That optimization matters on large boards.

4. The binary trie and maximum XOR

A trie does not have to store letters. Store bits, and it indexes numbers. The famous problem: given an array of non-negative integers, find the maximum value of a ^ b over all pairs.

Brute force: try every pair: O(nยฒ).

Better: write each number as a fixed-width binary string (most significant bit first) and insert it into a trie with two possible children, 0 and 1. To find the best partner for x, walk down the trie, and at each bit prefer the opposite bit (it makes that bit of the XOR equal to 1). If the opposite branch is missing, take the same bit. Each query takes O(B) steps where B is the number of bits, so the whole algorithm is O(n ร— B), effectively O(n).

TEXT
numbers (5 bits): 5 = 00101    25 = 11001

query x = 5:  want opposite of 0,0,1,0,1  ->  1,1,0,1,0
the trie holds 25 = 11001: follows 1,1,0 (opposite), 0 (not opposite, forced), 1 (forced)
XOR so far: 1 1 1 0 0 = 28
Python Maximum XOR of two numbers with a bit trie

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same idea answers "maximum XOR with a given value in a range" and many subarray-XOR problems, since a prefix XOR array turns subarray XOR into the XOR of two prefix values (see Prefix Sums for the sum version of that trick).

5. Longest prefix match (routing)

Internet routers hold a table of address prefixes (like 10.1.0.0/16) and must pick the longest matching prefix for each packet. A binary trie over the address bits does it in O(address length): walk the bits, remember the last node that holds a route, and return it when the walk ends.

Python Longest prefix match on bit strings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

6. Compressed tries (radix trees)

Many trie nodes have exactly one child. Storing a node for each letter of "extraordinary" after its unique branch point wastes memory. A radix tree (also called a compressed or Patricia trie) merges every chain of single-child nodes into one edge labeled with a whole string.

TEXT
Plain trie for: romane, romanus, romulus       Radix tree

 r                                             (root)
 โ””โ”€โ”€ o                                          โ””โ”€โ”€ "rom"
      โ””โ”€โ”€ m                                          โ”œโ”€โ”€ "an"
           โ”œโ”€โ”€ a                                     โ”‚     โ”œโ”€โ”€ "e"*
           โ”‚    โ””โ”€โ”€ n                                โ”‚     โ””โ”€โ”€ "us"*
           โ”‚         โ”œโ”€โ”€ e*                          โ””โ”€โ”€ "ulus"*
           โ”‚         โ””โ”€โ”€ u
           โ”‚              โ””โ”€โ”€ s*
           โ””โ”€โ”€ u
                โ””โ”€โ”€ l
                     โ””โ”€โ”€ u
                          โ””โ”€โ”€ s*

The plain trie needs 12 nodes below the root for these three words; the radix tree needs 5. The number of radix nodes is at most about 2 ร— (number of words), instead of one per character. Operations remain O(L) in characters compared, but with far fewer node hops.

The tricky part is insertion: when a new word shares only part of an edge label, you must split the edge at the shared prefix.

Python A radix tree with edge splitting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the node count: a plain trie for the same eight words would need 29 nodes (one per distinct prefix, plus the root), while this radix tree needs only 14. Radix trees are used in IP routing tables, in the Linux kernel, and in key-value stores.

Choosing the right tool

Task Good tool
Exact word membership set
Prefix existence, autocomplete Trie
Prefix queries with sorted static data Sorted list + bisect
Many words, long unique tails, memory matters Radix tree
Max/min XOR, bit prefix problems Binary trie
Search many patterns at once in text Aho-Corasick (trie + failure links), see Pattern Matching

Common mistakes

  • Not pruning in Word Search II. Running a separate DFS per word is the brute force; always follow trie edges and stop when the child is missing.
  • Forgetting to unmark cells when backtracking, which hides valid paths.
  • Variable bit width in a binary trie. All numbers must be inserted with the same width, or the high bits mismatch. Negative numbers need special handling (offset them or treat the sign bit separately).
  • Preferring the same bit instead of the opposite in the XOR query. Maximizing XOR means choosing the different bit whenever possible.
  • Mishandling radix splits: forgetting to keep the old subtree on the lower half of a split edge loses words.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In autocomplete, why is walking to the prefix node faster than scanning every word?

    The trie jumps directly to the subtree of matching words, so non-matching words are never touched.
  2. 2. In the maximum-XOR trie, which bit should the query prefer at each level?

    XOR gives 1 only where the bits differ, so choosing the opposite bit makes that position of the result 1.
  3. 3. What is the time complexity of the trie solution for maximum XOR of n numbers with B bits?

    Each of the n numbers is inserted and queried once, each taking B steps down the trie.
  4. 4. Why is a trie useful in Word Search II?

    Without a trie you repeat the board search for each word; with it, shared prefixes are explored once and dead ends stop immediately.
  5. 5. What does a radix tree do to a chain of single-child nodes?

    Compressing chains cuts the node count to at most about twice the number of words.

Summary

  • Rank autocomplete results by storing frequencies on word-end nodes and using heapq.nsmallest for the top k.
  • The longest common prefix is where the trie path first forks or a word ends; a direct comparison is simpler for a single query.
  • Word Search II runs one backtracking search guided by a trie, pruning every path that is not a prefix of some word.
  • A binary trie over fixed-width bit strings solves maximum XOR in O(n ร— B) by preferring opposite bits.
  • Longest prefix match, as used in routing, remembers the deepest route seen while walking the bits.
  • A radix tree compresses single-child chains into string-labeled edges; inserting may split an edge.

Next: Segment Trees