This gist implements a Trie (prefix tree) structure and integrates it into a React component to provide autocomplete functionality. The Trie structure efficiently stores and retrieves words, making it ideal for autocomplete and search applications. The React component uses the Trie to suggest completions for user input in real time.

autocomplete-input.tsx

'use client';

import React from 'react';

import { cn } from './utils';

export type AutocompleteInputProps =
  React.InputHTMLAttributes<HTMLInputElement> & {
    suggestion: string;
  };

const AutocompleteInput = React.forwardRef<
  HTMLInputElement,
  AutocompleteInputProps
>(({ className, type, suggestion, ...props }, ref) => {
  const { value, onChange, onKeyDown } = props;

  return (
    <div className="relative">
      <input
        type={type}
        value={value}
        className={cn(
          'border-input placeholder:text-muted-foreground/70 focus-visible:ring-ring focus-visible:border-primary flex h-9 w-full rounded-sm border bg-transparent px-3 py-1 text-sm transition-colors file:border-0 file:bg-transparent file:text-sm file:font-medium focus-visible:outline-none focus-visible:ring-1 disabled:cursor-not-allowed disabled:opacity-50',
          className
        )}
        ref={ref}
        onChange={onChange}
        onKeyDown={onKeyDown}
        {...props}
      />
      <input
        type={type}
        value={suggestion}
        className={cn(
          'border-input placeholder:text-muted-foreground/70 focus-visible:ring-ring focus-visible:border-primary flex h-9 w-full rounded-sm border bg-transparent px-3 py-1 text-sm transition-colors file:border-0 file:bg-transparent file:text-sm file:font-medium focus-visible:outline-none focus-visible:ring-1 disabled:cursor-not-allowed disabled:opacity-50 break-words absolute top-0 left-0 bg-transparent -z-10 text-muted-foreground/80 cursor-none',
          className
        )}
        readOnly
      />
    </div>
  );
});
AutocompleteInput.displayName = 'AutocompleteInput';

export { AutocompleteInput };

page.tsx

'use client';

import React, { useEffect, useState } from 'react';
import { zodResolver } from '@hookform/resolvers/zod';
import { SubmitHandler, useForm } from 'react-hook-form';
import { z } from 'zod';

import { apiClient } from './lib/api-client'; // imaginary api client for your backend
import { categoriesTrie, initializeCategoriesTrie } from './utils';

import { useDebounce } from './use-debounce';

import { AutocompleteInput } from '@/components/ui/autocomplete-input';
import { Button } from '@/components/ui/button';
import {
  Form,
  FormControl,
  FormField,
  FormItem,
  FormLabel,
} from '@/components/ui/form';

const FormSchema = z.object({
  category: z.string().optional(),
  unit: z.string().optional(),
});

type FormValues = z.infer<typeof FormSchema>;

export default function TestPage() {
  const [categoryPrefix, setCategoryPrefix] = useState<string>('');
  const [categorySuggestion, setCategorySuggestion] = useState<string>('');
  const [categorySuggestions, setCategorySuggestions] = useState<string[]>([]);

  const form = useForm<FormValues>({
    resolver: zodResolver(FormSchema),
    defaultValues: {
      category: '',
      unit: '',
    },
  });

  const { control, handleSubmit, setValue } = form;

  // Imaginary backend API call to fetch category suggestions.
  const categorySuggestionsQuery = apiClient.categories.suggestions.useQuery({
    teamId: 'clvf4i3g000087l65rj06d1mz',
  });

  const debouncedCategoryPrefix = useDebounce(categoryPrefix, 30);

  useEffect(() => {
    if (categorySuggestionsQuery.data) {
      setCategorySuggestions(categorySuggestionsQuery.data.words);
    }
  }, [categorySuggestionsQuery.data]);

  useEffect(() => {
    if (categorySuggestions.length > 0) {
      initializeCategoriesTrie(categorySuggestions);
    }
  }, [categorySuggestions]);

  useEffect(() => {
    if (debouncedCategoryPrefix) {
      const words = debouncedCategoryPrefix.split(' ');
      const triePrefix = words[words.length - 1].toLowerCase();
      const foundWords = categoriesTrie
        .find(triePrefix)
        .sort((a, b) => a.length - b.length);
      const firstWord = foundWords[0];
      if (
        foundWords.length !== 0 &&
        debouncedCategoryPrefix !== '' &&
        debouncedCategoryPrefix[debouncedCategoryPrefix.length - 1] !== ' '
      ) {
        if (firstWord != null) {
          const remainder = firstWord.slice(triePrefix.length);
          setCategorySuggestion(debouncedCategoryPrefix + remainder);
        }
      } else {
        setCategorySuggestion(debouncedCategoryPrefix);
      }
    } else {
      setCategorySuggestion(debouncedCategoryPrefix);
    }
  }, [debouncedCategoryPrefix]);

  const handleKeyDownCategory = (e: React.KeyboardEvent<HTMLInputElement>) => {
    if (e.keyCode === 32) {
      // Space bar pressed
      const trimmedValue = categoryPrefix.trimEnd(); // Remove trailing spaces
      setCategoryPrefix(trimmedValue);
      setValue('category', trimmedValue); // Update the form value without trailing spaces
    }
    if (e.keyCode === 39) {
      // Right arrow key pressed
      setCategoryPrefix(categorySuggestion);
      setValue('category', categorySuggestion); // Update the form value
    }
  };

  const onSubmit: SubmitHandler<FormValues> = async (data) => {
    console.log(data);
  };

  return (
    <div>
      <div className="flex flex-col min-h-screen px-8 py-4">
        <Form {...form}>
          <div className="flex flex-col space-y-6">
            <FormField
              control={control}
              name="category"
              render={({ field }) => (
                <FormItem>
                  <FormLabel htmlFor="category">Category</FormLabel>
                  <FormControl>
                    <AutocompleteInput
                      value={field.value}
                      suggestion={categorySuggestion}
                      placeholder="Category"
                      onChange={(e) => {
                        field.onChange(e.target.value);
                        setCategoryPrefix(e.target.value);
                        setValue('category', e.target.value);
                      }}
                      onKeyDown={handleKeyDownCategory}
                      className="w-80"
                    />
                  </FormControl>
                </FormItem>
              )}
            />

            <Button onClick={handleSubmit(onSubmit)} className="w-32">
              Submit
            </Button>
          </div>
        </Form>
      </div>
    </div>
  );
}

trie.ts

// prefix tree

type TrieNode = {
  letter: string | null;
  prevLetter: TrieNode | null;
  nextLetters: Record<string, TrieNode>;
  isComplete: boolean;
  getWord: () => string;
}

type Trie = {
  root: TrieNode;
  insert: (word: string) => void;
  contains: (word: string) => boolean;
  find: (prefix: string) => string[];
  findAllWords: (node: TrieNode, arr: string[]) => void;
}

/**
 * Represents a node in the Trie.
 * @constructor
 * @param {string} letter - The letter this node represents.
 */
function TrieNode(letter: string | null) {
  // properties
  this.letter = letter; // The letter this node represents.
  this.prevLetter = null; // The previous node in the Trie.
  this.nextLetters = {}; // The next nodes in the Trie.
  this.isComplete = false; // Indicates whether this node completes a word.

  //methods
  this.getWord = getWord;

  /**
   * Iterates through nodes to get word prediction.
   * @return {string} The word this node completes.
   */
  function getWord(): string {
    var node = this;
    var wordLetters: any[] = [];
    while (node.prevLetter) {
      wordLetters.unshift(node.letter);
      node = node.prevLetter; // set the previous letter as node.
    }
    return wordLetters.join('');
  }
}

/**
 * Represents a Trie (prefix tree).
 * @constructor
 */
export function Trie() {
  // properties
  this.root = new TrieNode(null); // The root node of the Trie.

  // methods
  this.insert = insert; // Inserts a new word in the Trie.
  this.contains = contains; // Checks if a word exists in the Trie.
  this.find = find; // Finds words in the Trie that start with the given prefix.

  /**
   * Inserts a new word in the Trie.
   * @param {string} word - The word to insert.
   * @returns {void}
   */
  function insert(word: string): void {
    var node = this.root; // set first node to root node
    for (let i = 0; i < word.length; i++) {
      const current_letter = word[i];
      if (!node.nextLetters[current_letter]) {
        // if letter not in next letters
        node.nextLetters[current_letter] = new TrieNode(current_letter); // make it node
        node.nextLetters[current_letter].prevLetter = node; // add it as a child node
      }
      node = node.nextLetters[current_letter]; // reset node to current letter & continue iteration

      // check whether whole word is inserted
      if (i === word.length - 1) {
        node.isComplete = true;
      }
    }
  }

  /**
   * Checks if a word exists in the Trie.
   * @param {string} word - The word to check.
   * @returns {boolean} Whether the word exists in the Trie.
   */
  function contains(word: string): boolean {
    var node = this.root; // set first node to root node
    for (let i = 0; i < word.length; i++) {
      const current_letter = word[i];
      let next_node = node.nextLetters[current_letter];
      if (next_node) {
        // if letter is one of next letters
        node = next_node; // set it as a next node
      } else {
        return false;
      }
    }
    return node.isComplete; // definitely returns 'true'
  }

  /**
   * Finds words in the Trie that start with the given prefix.
   * @param {string} clue_letters - The prefix to search for.
   * @returns {array} The words that start with the given prefix.
   */
  function find(clue_letters: string): string[] {
    var node = this.root; // set first node to root node
    var output = [];
    for (let i = 0; i < clue_letters.length; i++) {
      const clue_letter = clue_letters[i];
      let next_node = node.nextLetters[clue_letter];
      if (next_node) {
        // if clue letter is one of next letters
        node = next_node; // set it as next node
      } else {
        return output;
      }
    }

    // use the last node to find the next possible words.
    findAllWords(node, output);
    return output;
  }

  /**
   * Finds all words in the Trie.
   * @param {TrieNode} node - The node to start from.
   * @param {array} arr - The array to store the words.
   * @returns {array} The words that start with the given prefix.
   */
  function findAllWords(node: TrieNode, arr: string[]): void {
    if (node.isComplete) {
      // check if node is end node
      arr.unshift(node.getWord()); // get all words and add them to array
    }

    // otherwise recursively call the next nodes
    for (var next_letter in node.nextLetters) {
      findAllWords(node.nextLetters[next_letter], arr);
    }
  }
}

use-debounce.ts

import { useEffect, useState } from 'react';

/**
 * useDebounce - A custom hook that debounces a value by the given delay.
 *
 * @param {any} value - The value to debounce.
 * @param {number} delay - The debounce delay in milliseconds.
 * @returns {any} - The debounced value.
 */
export function useDebounce(value: any, delay: number): any {
  const [debouncedValue, setDebouncedValue] = useState(value);

  useEffect(() => {
    // Set a timeout to update the debounced value after the specified delay
    const handler = setTimeout(() => {
      setDebouncedValue(value);
    }, delay);

    // Cleanup the timeout if the value or delay changes
    return () => {
      clearTimeout(handler);
    };
  }, [value, delay]);

  return debouncedValue;
}

utils.ts

import { Trie } from './trie';

export function cn(...inputs: ClassValue[]) {
  return twMerge(clsx(inputs));
}

export const categoriesTrie = new Trie();

export const initializeCategoriesTrie = async (categoriesSuggestions: any) => {
  const words = categoriesSuggestions;
  for (let i = 0; i < words.length; i++) {
    const word = words[i];
    categoriesTrie.insert(word);
  }
};