Sort an Array of Strings Using a Trie

Given a list of lowercase words, return them sorted in lexicographic (dictionary) order. Duplicates must be kept.

Example

Input:  ["the", "a", "there", "answer", "any", "by", "bye", "their", "a"]
Output: ["a", "a", "answer", "any", "by", "bye", "the", "their", "there"]

Lexicographic order compares words character by character, and a word comes before any longer word it's a prefix of: "the" < "their" < "there".

Brute force: comparison sort

List.sort(null) (or Collections.sort) orders String values by comparing their characters from the left. For lowercase words this is lexicographic order, and a shorter word sorts before a longer word it is a prefix of.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static List<String> sortWords(String[] words) {
        List<String> sorted = new ArrayList<>(List.of(words));
        Collections.sort(sorted);
        return sorted;
    }

    public static void main(String[] args) {
        System.out.println(sortWords(new String[] {"the", "a", "there", "answer", "any", "by", "bye", "their", "a"}));
    }
}

[a, a, answer, any, by, bye, the, their, there]

Time: O(L · n log n): n log n comparisons, and each comparison can look at up to L characters. Space: O(n) for the list (the strings themselves are shared, not copied).

With a trie: insert everything, then walk in alphabetical order

A trie already keeps its words in sorted order: a depth-first walk that visits children from a to z meets the words in lexicographic order. Two details:

• Duplicates: replace the isEnd flag with a count, and output the word count times.
• Prefixes first: output a node's own words before visiting its children. That puts "the" before "their" and "there".

A trie node is an object with an array of 26 child references. A slot is null until a word needs that child, so no Option or Box wrapper is needed.

Walkthrough of the walk under t → h → e:

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int count; // how many inserted words end at this node
    }

    static void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.count++;
    }

    static void walk(TrieNode node, StringBuilder buf, List<String> out) {
        for (int k = 0; k < node.count; k++) {
            out.add(buf.toString()); // this node's words come before its children's
        }
        for (int i = 0; i < 26; i++) {
            TrieNode child = node.children[i];
            if (child != null) {
                buf.append((char) ('a' + i));
                walk(child, buf, out);
                buf.deleteCharAt(buf.length() - 1);
            }
        }
    }

    static List<String> sortWords(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            insert(root, w);
        }
        List<String> out = new ArrayList<>(words.length);
        walk(root, new StringBuilder(), out);
        return out;
    }

    public static void main(String[] args) {
        System.out.println(sortWords(new String[] {"the", "a", "there", "answer", "any", "by", "bye", "their", "a"}));
    }
}

[a, a, answer, any, by, bye, the, their, there]

Time: O(C) to insert, where C is the total number of characters, plus O(N · 26) for the walk over N nodes, plus the output. No comparisons between words are needed. Space: O(C) for the trie in the worst case.

In practice, Collections.sort on a list of strings is usually faster, because the trie allocates one node (with a 26-slot array) per character and the walk is not cache-friendly. The trie pays off when you also need prefix queries on the same data, or when the words share long prefixes. This is the same idea as radix sort: ordering by characters instead of comparing whole keys.

Edge cases

• Empty list: empty output.
• Duplicates: kept, through the count.
• The empty string "": it ends at the root, so the root's count is 1, and it's output first, which is correct since "" sorts before every other word.
• Characters outside a to z: the trie index word.charAt(i) - 'a' would be out of range, so the trie version needs lowercase input, as the problem states.