Back to Repositories

Testing Trie Data Structure Implementation in javascript-algorithms

This test suite validates the implementation of a Trie data structure in JavaScript, covering core operations like word addition, deletion, and character suggestion functionality. The tests ensure proper tree construction and traversal while maintaining data integrity.

Test Coverage Overview

The test suite provides comprehensive coverage of Trie operations:

Trie initialization and structure validation
Word addition with character node linking
Word deletion with proper node cleanup
Character suggestion functionality
Word existence verification

Edge cases include empty trie handling, non-existent word deletion, and partial word matching.

Implementation Analysis

The testing approach utilizes Jest’s describe/it pattern for organized test grouping. Each test case validates specific Trie operations through explicit state verification and assertion chains. The implementation leverages Jest’s expect API for detailed node structure validation and string matching.

Technical Details

Testing Framework: Jest

Assertion Methods: toBe(), toEqual(), toBeNull()
Test Structure: describe/it blocks
Custom toString() methods for node inspection
Node traversal verification through getChild() calls

Best Practices Demonstrated

The test suite exemplifies strong testing practices:

Isolated test cases with clear objectives
Thorough state verification after operations
Progressive complexity in test scenarios
Comprehensive edge case coverage
Clear test descriptions and maintainable structure

trekhleb/javascript-algorithms

src/data-structures/trie/__test__/Trie.test.js

            
import Trie from '../Trie';

describe('Trie', () => {
  it('should create trie', () => {
    const trie = new Trie();

    expect(trie).toBeDefined();
    expect(trie.head.toString()).toBe('*');
  });

  it('should add words to trie', () => {
    const trie = new Trie();

    trie.addWord('cat');

    expect(trie.head.toString()).toBe('*:c');
    expect(trie.head.getChild('c').toString()).toBe('c:a');

    trie.addWord('car');
    expect(trie.head.toString()).toBe('*:c');
    expect(trie.head.getChild('c').toString()).toBe('c:a');
    expect(trie.head.getChild('c').getChild('a').toString()).toBe('a:t,r');
    expect(trie.head.getChild('c').getChild('a').getChild('t').toString()).toBe('t*');
  });

  it('should delete words from trie', () => {
    const trie = new Trie();

    trie.addWord('carpet');
    trie.addWord('car');
    trie.addWord('cat');
    trie.addWord('cart');
    expect(trie.doesWordExist('carpet')).toBe(true);
    expect(trie.doesWordExist('car')).toBe(true);
    expect(trie.doesWordExist('cart')).toBe(true);
    expect(trie.doesWordExist('cat')).toBe(true);

    // Try to delete not-existing word first.
    trie.deleteWord('carpool');
    expect(trie.doesWordExist('carpet')).toBe(true);
    expect(trie.doesWordExist('car')).toBe(true);
    expect(trie.doesWordExist('cart')).toBe(true);
    expect(trie.doesWordExist('cat')).toBe(true);

    trie.deleteWord('carpet');
    expect(trie.doesWordExist('carpet')).toEqual(false);
    expect(trie.doesWordExist('car')).toEqual(true);
    expect(trie.doesWordExist('cart')).toBe(true);
    expect(trie.doesWordExist('cat')).toBe(true);

    trie.deleteWord('cat');
    expect(trie.doesWordExist('car')).toEqual(true);
    expect(trie.doesWordExist('cart')).toBe(true);
    expect(trie.doesWordExist('cat')).toBe(false);

    trie.deleteWord('car');
    expect(trie.doesWordExist('car')).toEqual(false);
    expect(trie.doesWordExist('cart')).toBe(true);

    trie.deleteWord('cart');
    expect(trie.doesWordExist('car')).toEqual(false);
    expect(trie.doesWordExist('cart')).toBe(false);
  });

  it('should suggests next characters', () => {
    const trie = new Trie();

    trie.addWord('cat');
    trie.addWord('cats');
    trie.addWord('car');
    trie.addWord('caption');

    expect(trie.suggestNextCharacters('ca')).toEqual(['t', 'r', 'p']);
    expect(trie.suggestNextCharacters('cat')).toEqual(['s']);
    expect(trie.suggestNextCharacters('cab')).toBeNull();
  });

  it('should check if word exists', () => {
    const trie = new Trie();

    trie.addWord('cat');
    trie.addWord('cats');
    trie.addWord('carpet');
    trie.addWord('car');
    trie.addWord('caption');

    expect(trie.doesWordExist('cat')).toBe(true);
    expect(trie.doesWordExist('cats')).toBe(true);
    expect(trie.doesWordExist('carpet')).toBe(true);
    expect(trie.doesWordExist('car')).toBe(true);
    expect(trie.doesWordExist('cap')).toBe(false);
    expect(trie.doesWordExist('call')).toBe(false);
  });
});