What

Brief

This is a standalone Trie data structure from the data-structure-typed collection. If you wish to access more data structures or advanced features, you can transition to directly installing the complete data-structure-typed package

How

install

npm

npm i trie-typed --save

yarn

yarn add trie-typed

snippet

basic Trie creation and add words

 // Create a simple Trie with initial words
    const trie = new Trie(['apple', 'app', 'apply']);

    // Verify size
    console.log(trie.size); // 3;

    // Check if words exist
    console.log(trie.has('apple')); // true;
    console.log(trie.has('app')); // true;

    // Add a new word
    trie.add('application');
    console.log(trie.size); // 4;

Trie getWords and prefix search

 const trie = new Trie(['apple', 'app', 'apply', 'application', 'apricot']);

    // Get all words with prefix 'app'
    const appWords = trie.getWords('app');
    console.log(appWords); // contains 'app';
    console.log(appWords); // contains 'apple';
    console.log(appWords); // contains 'apply';
    console.log(appWords); // contains 'application';
    expect(appWords).not.toContain('apricot');

Trie isPrefix and isAbsolutePrefix checks

 const trie = new Trie(['tree', 'trial', 'trick', 'trip', 'trie']);

    // Check if string is a prefix of any word
    console.log(trie.hasPrefix('tri')); // true;
    console.log(trie.hasPrefix('tr')); // true;
    console.log(trie.hasPrefix('xyz')); // false;

    // Check if string is an absolute prefix (not a complete word)
    console.log(trie.hasPurePrefix('tri')); // true;
    console.log(trie.hasPurePrefix('tree')); // false; // 'tree' is a complete word

    // Verify size
    console.log(trie.size); // 5;

Trie delete and iteration

 const trie = new Trie(['car', 'card', 'care', 'careful', 'can', 'cat']);

    // Delete a word
    trie.delete('card');
    console.log(trie.has('card')); // false;

    // Word with same prefix still exists
    console.log(trie.has('care')); // true;

    // Size decreased
    console.log(trie.size); // 5;

    // Iterate through all words
    const allWords = [...trie];
    console.log(allWords.length); // 5;

Trie for autocomplete search index

 // Trie is perfect for autocomplete: O(m + k) where m is prefix length, k is results
    const searchIndex = new Trie(['typescript', 'javascript', 'python', 'java', 'rust', 'ruby', 'golang', 'kotlin']);

    // User types 'j' - get all suggestions
    const jResults = searchIndex.getWords('j');
    console.log(jResults); // contains 'javascript';
    console.log(jResults); // contains 'java';
    console.log(jResults.length); // 2;

    // User types 'ja' - get more specific suggestions
    const jaResults = searchIndex.getWords('ja');
    console.log(jaResults); // contains 'javascript';
    console.log(jaResults); // contains 'java';
    console.log(jaResults.length); // 2;

    // User types 'jav' - even more specific
    const javResults = searchIndex.getWords('jav');
    console.log(javResults); // contains 'javascript';
    console.log(javResults); // contains 'java';
    console.log(javResults.length); // 2;

    // Check for common prefix

    console.log(searchIndex.hasCommonPrefix('ja')); // false; // Not all words start with 'ja'

    // Total words in index
    console.log(searchIndex.size); // 8;

    // Get height (depth of tree)
    const height = searchIndex.getHeight();
    console.log(typeof height); // 'number';

Dictionary: Case-insensitive word lookup

 // Create a case-insensitive dictionary
    const dictionary = new Trie<string>([], { caseSensitive: false });

    // Add words with mixed casing
    dictionary.add('Hello');
    dictionary.add('WORLD');
    dictionary.add('JavaScript');

    // Test lookups with different casings
    console.log(dictionary.has('hello')); // true;
    console.log(dictionary.has('HELLO')); // true;
    console.log(dictionary.has('Hello')); // true;
    console.log(dictionary.has('javascript')); // true;
    console.log(dictionary.has('JAVASCRIPT')); // true;

File System Path Operations

 const fileSystem = new Trie<string>([
      '/home/user/documents/file1.txt',
      '/home/user/documents/file2.txt',
      '/home/user/pictures/photo.jpg',
      '/home/user/pictures/vacation/',
      '/home/user/downloads'
    ]);

    // Find common directory prefix
    console.log(fileSystem.getLongestCommonPrefix()); // '/home/user/';

    // List all files in a directory
    const documentsFiles = fileSystem.getWords('/home/user/documents/');
    console.log(documentsFiles); // ['/home/user/documents/file1.txt', '/home/user/documents/file2.txt'];

IP Address Routing Table

 // Add IP address prefixes and their corresponding routes
    const routes = {
      '192.168.1': 'LAN_SUBNET_1',
      '192.168.2': 'LAN_SUBNET_2',
      '10.0.0': 'PRIVATE_NETWORK_1',
      '10.0.1': 'PRIVATE_NETWORK_2'
    };

    const ipRoutingTable = new Trie<string>(Object.keys(routes));

    // Check IP address prefix matching
    console.log(ipRoutingTable.hasPrefix('192.168.1')); // true;
    console.log(ipRoutingTable.hasPrefix('192.168.2')); // true;

    // Validate IP address belongs to subnet
    const ip = '192.168.1.100';
    const subnet = ip.split('.').slice(0, 3).join('.');
    console.log(ipRoutingTable.hasPrefix(subnet)); // true;

API docs & Examples

API Docs

Live Examples

Examples Repository

Data Structures

Standard library data structure comparison

Benchmark

Built-in classic algorithms

Software Engineering Design Standards