Prefix tree for autocomplete

Trie.java

package org.example.structures.tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;


public class Trie {

    public static class Node {
        public final char key;
        public final Map<Character, Node> children;

        public Node(char c) {
            this.key = c;
            this.children = new HashMap<>();
        }

        @Override
        public String toString() {
            return "(%c, %s)".formatted(key, children);
        }
    }

    private Map<Character, Node> root = new HashMap<>();

    public void add(String word) {
        var current = root;
        for (var c: word.toCharArray()) {
            if (!current.containsKey(c)) {
                current.put(c, new Node(c));
            }
            current = current.get(c).children;
        }
        current.put('$', new Node('$'));
    }

    public void add(String ...words) {
        for (var w: words) {
            add(w);
        }
    }

    public List<String> complete(String prefix) {
        var result = new LinkedList<String>();

        var current = root;
        for (var c: prefix.toCharArray()) {
            if (!current.containsKey(c)) {
                break;
            }
            current = current.get(c).children;
        }

        for (var c: current.keySet()) {
            var path = new LinkedList<Node>();
            var visited = new HashSet<Node>();
            path.add(current.get(c));

            while (!path.isEmpty()) {
                var tail = path.getLast();

                var unseenChild = tail.children.values().stream()
                        .filter(n -> !visited.contains(n))
                        .findFirst()
                        .orElse(null);

                if (unseenChild != null) {
                    path.add(unseenChild);
                } else {
                    if (tail.children.isEmpty()) {
                        var seq = path.stream().map(n -> n.key).reduce("", (str, chr) -> str + chr, (s1, s2) -> s1 + s2);
                        result.add(prefix + trim$(seq));
                    }
                    visited.add(path.removeLast());
                }
            }
        }

        return result;
    }

    public static String trim$(String s) {
        if (s != null && s.charAt(s.length() - 1) == '$') {
            return s.substring(0, s.length() - 1);
        }
        return s;
    }

    public static void main(String[] args) {
        var t = new Trie();
        t.add("hi", "hello", "hell", "head", "help");

        System.out.println(t.complete("hel"));
    }

}