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 
  private static final class Node {
      final Map<Character, Node> children = new HashMap<>();
      boolean isWord;
      int frequency;
  }
13 
  private final Node root = new Node();
15 
  public void insert(String word) {
      Node node = root;
      for (char c : word.toCharArray()) {
          node = node.children.computeIfAbsent(c, k -> new Node());
      }
      node.isWord = true;
      node.frequency++;
  }
24 
  public List<String> suggest(String prefix, int limit) {
      List<String> results = new ArrayList<>();
      Node node = root;
      for (char c : prefix.toCharArray()) {
          node = node.children.get(c);
          if (node == null) {
              return results;
          }
      }
      collect(node, new StringBuilder(prefix), results, limit);
      return results;
  }
37 
  private void collect(Node node, StringBuilder path, List<String> out, int limit) {
      if (out.size() >= limit) {
          return;
      }
      if (node.isWord) {
          out.add(path.toString());
      }
      for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
          path.append(entry.getKey());
          collect(entry.getValue(), path, out, limit);
          path.deleteCharAt(path.length() - 1);
      }
  }
51}

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

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

Related explainers

java

public interface GitHubClient {
 
    @GetExchange("/users/{username}")
    GitHubUser getUser(@PathVariable String username);

Declarative HTTP clients in Spring

http-client declarative-api proxy

Intermediate 8 steps

ruby

class KeyTransformer
  def self.camelize(data)
    new.camelize(data)
  end

Recursively camelizing nested Ruby data

recursion data-transformation pattern-matching

Intermediate 7 steps

java

@RestController
@RequestMapping("/api/products")
public class ProductSearchController {

Binding collection query params in Spring

rest-api query-parameters dependency-injection

Intermediate 6 steps

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

Evaluating math expressions with two stacks

stacks parsing operator-precedence

Intermediate 9 steps

java

@Entity
@Table(name = "orders")
@SQLDelete(sql = "UPDATE orders SET deleted = true, deleted_at = now() WHERE id = ?")
@Where(clause = "deleted = false")

Soft deletes with Hibernate in Spring

soft-delete jpa hibernate

Intermediate 9 steps

java

@GetMapping("/files/{id}")
public ResponseEntity<StreamingResponseBody> download(
        @PathVariable String id,
        @RequestHeader(value = HttpHeaders.RANGE, required = false) String rangeHeader) throws IOException {