Back to Repositories

Testing Binary Search Tree Implementation in javascript-algorithms

This test suite validates the core functionality of a Binary Search Tree implementation, ensuring proper node insertion, removal, traversal, and custom object handling. The tests verify both basic operations and advanced tree manipulation scenarios.

Test Coverage Overview

The test suite provides comprehensive coverage of Binary Search Tree operations:

Basic tree initialization and structure validation
Node insertion with numeric and object values
Value existence checking
Node removal with tree rebalancing
Tree traversal and sorting validation
Height calculation verification

Implementation Analysis

The testing approach utilizes Jest’s describe/it pattern for structured test organization. Each test case isolates specific BST operations, employing both simple numeric values and complex object scenarios with custom comparator functions.

The implementation validates both structural integrity and functional behavior, using Jest’s expect assertions for precise state verification.

Technical Details

Testing Framework: Jest

Assertion methods: toBeDefined(), toBe(), toBeNull()
Custom object comparison implementation
String representation testing via toString()
Height property validation

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Isolated test cases for individual operations
Progressive complexity in test scenarios
Comprehensive edge case coverage
Clear test case descriptions
Verification of both state and behavior

trekhleb/javascript-algorithms

src/data-structures/tree/binary-search-tree/__test__/BinarySearchTree.test.js

            
import BinarySearchTree from '../BinarySearchTree';

describe('BinarySearchTree', () => {
  it('should create binary search tree', () => {
    const bst = new BinarySearchTree();

    expect(bst).toBeDefined();
    expect(bst.root).toBeDefined();
    expect(bst.root.value).toBeNull();
    expect(bst.root.left).toBeNull();
    expect(bst.root.right).toBeNull();
  });

  it('should insert values', () => {
    const bst = new BinarySearchTree();

    const insertedNode1 = bst.insert(10);
    const insertedNode2 = bst.insert(20);
    bst.insert(5);

    expect(bst.toString()).toBe('5,10,20');
    expect(insertedNode1.value).toBe(10);
    expect(insertedNode2.value).toBe(20);
  });

  it('should check if value exists', () => {
    const bst = new BinarySearchTree();

    bst.insert(10);
    bst.insert(20);
    bst.insert(5);

    expect(bst.contains(20)).toBe(true);
    expect(bst.contains(40)).toBe(false);
  });

  it('should remove nodes', () => {
    const bst = new BinarySearchTree();

    bst.insert(10);
    bst.insert(20);
    bst.insert(5);

    expect(bst.toString()).toBe('5,10,20');

    const removed1 = bst.remove(5);
    expect(bst.toString()).toBe('10,20');
    expect(removed1).toBe(true);

    const removed2 = bst.remove(20);
    expect(bst.toString()).toBe('10');
    expect(removed2).toBe(true);
  });

  it('should insert object values', () => {
    const nodeValueCompareFunction = (a, b) => {
      const normalizedA = a || { value: null };
      const normalizedB = b || { value: null };

      if (normalizedA.value === normalizedB.value) {
        return 0;
      }

      return normalizedA.value < normalizedB.value ? -1 : 1;
    };

    const obj1 = { key: 'obj1', value: 1, toString: () => 'obj1' };
    const obj2 = { key: 'obj2', value: 2, toString: () => 'obj2' };
    const obj3 = { key: 'obj3', value: 3, toString: () => 'obj3' };

    const bst = new BinarySearchTree(nodeValueCompareFunction);

    bst.insert(obj2);
    bst.insert(obj3);
    bst.insert(obj1);

    expect(bst.toString()).toBe('obj1,obj2,obj3');
  });

  it('should be traversed to sorted array', () => {
    const bst = new BinarySearchTree();

    bst.insert(10);
    bst.insert(-10);
    bst.insert(20);
    bst.insert(-20);
    bst.insert(25);
    bst.insert(6);

    expect(bst.toString()).toBe('-20,-10,6,10,20,25');
    expect(bst.root.height).toBe(2);

    bst.insert(4);

    expect(bst.toString()).toBe('-20,-10,4,6,10,20,25');
    expect(bst.root.height).toBe(3);
  });
});