java 51 lines · 8 steps

Building a trie for autocomplete in Java

A prefix tree that stores words character by character and walks its branches to suggest completions.

Explained by highlit
Intermediate trie prefix-tree recursion autocomplete tree-traversal
1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5 
6public class AutocompleteTrie {
7 
8 private static final class Node {
9 final Map<Character, Node> children = new HashMap<>();
10 boolean isWord;
11 int frequency;
12 }
13 
14 private final Node root = new Node();
15 
16 public void insert(String word) {
17 Node node = root;
18 for (char c : word.toCharArray()) {
19 node = node.children.computeIfAbsent(c, k -> new Node());
20 }
21 node.isWord = true;
22 node.frequency++;
23 }
24 
25 public List<String> suggest(String prefix, int limit) {
26 List<String> results = new ArrayList<>();
27 Node node = root;
28 for (char c : prefix.toCharArray()) {
29 node = node.children.get(c);
30 if (node == null) {
31 return results;
32 }
33 }
34 collect(node, new StringBuilder(prefix), results, limit);
35 return results;
36 }
37 
38 private void collect(Node node, StringBuilder path, List<String> out, int limit) {
39 if (out.size() >= limit) {
40 return;
41 }
42 if (node.isWord) {
43 out.add(path.toString());
44 }
45 for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
46 path.append(entry.getKey());
47 collect(entry.getValue(), path, out, limit);
48 path.deleteCharAt(path.length() - 1);
49 }
50 }
51}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1A trie shares common prefixes across words so lookups depend on prefix length, not the size of the dictionary.
  2. 2Backtracking with a mutable StringBuilder rebuilds each word's path while reusing one buffer across the whole traversal.
  3. 3Passing a limit down the recursion lets you stop collecting suggestions as soon as you have enough.

Related explainers

java 
@Component
@Converter
public class EncryptedStringConverter implements AttributeConverter<String, String> {
 

Transparent column encryption in Spring & JPA

encryption aes-gcm jpa-converter
Advanced 10 steps
javascript 
function evaluate(expression) {
  const tokens = tokenize(expression);
  let pos = 0;
 

Building a recursive descent calculator

parsing recursion operator-precedence
Intermediate 8 steps
java 
package com.acme.billing.config;
 
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.ConfigurationProperties;

Feature-flagged beans with Spring @ConditionalOnProperty

feature-flags conditional-beans strategy-pattern
Intermediate 5 steps
java 
public static Map<String, String> parseCookieHeader(String header) {
    Map<String, String> cookies = new LinkedHashMap<>();
    if (header == null || header.isBlank()) {
        return cookies;

Parsing an HTTP Cookie header in Java

string-parsing http url-decoding
Intermediate 6 steps
java 
public class TimedSocketReader {
 
    private static final int READ_TIMEOUT_MS = 5_000;
    private static final int CONNECT_TIMEOUT_MS = 3_000;

Reading a socket with connect and read timeouts

sockets timeouts io
Intermediate 8 steps
java 
public final class EncodingDetector {
 
    public enum Encoding {
        UTF_8, UTF_16LE, UTF_16BE, UTF_32LE, UTF_32BE, ASCII, UNKNOWN

Detecting text encoding from raw bytes in Java

byte-manipulation encoding-detection bitwise-operations
Intermediate 8 steps

Share this explainer

Here's the card — post it anywhere.

Building a trie for autocomplete in Java — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code