Back to Repositories

Testing Depth-First Search Implementation in javascript-algorithms

This test suite validates the depth-first search (DFS) implementation for binary trees, focusing on node traversal and customizable visiting logic. It ensures proper node entry/exit callbacks and verifies the traversal order through comprehensive test cases.

Test Coverage Overview

The test suite provides thorough coverage of DFS functionality:

Basic DFS traversal with node entry/exit tracking
Custom traversal logic implementation
Verification of node visit order
Edge case handling for tree branches

Implementation Analysis

The testing approach utilizes Jest’s mock functions to track node visitation patterns and verify traversal order. It implements two main test scenarios: standard DFS traversal and customized traversal with conditional logic for specific branches.

Mock function implementation for callbacks
Binary tree construction and manipulation
Traversal order verification

Technical Details

Testing Framework: Jest
Mock Functions: jest.fn()
Data Structure: BinaryTreeNode
Test Setup: Individual node creation and tree construction
Assertion Methods: expect().toBe(), toHaveBeenCalledTimes()

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Isolated test cases with clear purposes
Comprehensive callback verification
Proper test setup and teardown
Clear and maintainable test structure
Effective use of mock functions

trekhleb/javascript-algorithms

src/algorithms/tree/depth-first-search/__test__/depthFirstSearch.test.js

            
import BinaryTreeNode from '../../../../data-structures/tree/BinaryTreeNode';
import depthFirstSearch from '../depthFirstSearch';

describe('depthFirstSearch', () => {
  it('should perform DFS operation on tree', () => {
    const nodeA = new BinaryTreeNode('A');
    const nodeB = new BinaryTreeNode('B');
    const nodeC = new BinaryTreeNode('C');
    const nodeD = new BinaryTreeNode('D');
    const nodeE = new BinaryTreeNode('E');
    const nodeF = new BinaryTreeNode('F');
    const nodeG = new BinaryTreeNode('G');

    nodeA.setLeft(nodeB).setRight(nodeC);
    nodeB.setLeft(nodeD).setRight(nodeE);
    nodeC.setLeft(nodeF).setRight(nodeG);

    // In-order traversing.
    expect(nodeA.toString()).toBe('D,B,E,A,F,C,G');

    const enterNodeCallback = jest.fn();
    const leaveNodeCallback = jest.fn();

    // Traverse tree without callbacks first to check default ones.
    depthFirstSearch(nodeA);

    // Traverse tree with callbacks.
    depthFirstSearch(nodeA, {
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
    });

    expect(enterNodeCallback).toHaveBeenCalledTimes(7);
    expect(leaveNodeCallback).toHaveBeenCalledTimes(7);

    // Check node entering.
    expect(enterNodeCallback.mock.calls[0][0].value).toEqual('A');
    expect(enterNodeCallback.mock.calls[1][0].value).toEqual('B');
    expect(enterNodeCallback.mock.calls[2][0].value).toEqual('D');
    expect(enterNodeCallback.mock.calls[3][0].value).toEqual('E');
    expect(enterNodeCallback.mock.calls[4][0].value).toEqual('C');
    expect(enterNodeCallback.mock.calls[5][0].value).toEqual('F');
    expect(enterNodeCallback.mock.calls[6][0].value).toEqual('G');

    // Check node leaving.
    expect(leaveNodeCallback.mock.calls[0][0].value).toEqual('D');
    expect(leaveNodeCallback.mock.calls[1][0].value).toEqual('E');
    expect(leaveNodeCallback.mock.calls[2][0].value).toEqual('B');
    expect(leaveNodeCallback.mock.calls[3][0].value).toEqual('F');
    expect(leaveNodeCallback.mock.calls[4][0].value).toEqual('G');
    expect(leaveNodeCallback.mock.calls[5][0].value).toEqual('C');
    expect(leaveNodeCallback.mock.calls[6][0].value).toEqual('A');
  });

  it('allow users to redefine node visiting logic', () => {
    const nodeA = new BinaryTreeNode('A');
    const nodeB = new BinaryTreeNode('B');
    const nodeC = new BinaryTreeNode('C');
    const nodeD = new BinaryTreeNode('D');
    const nodeE = new BinaryTreeNode('E');
    const nodeF = new BinaryTreeNode('F');
    const nodeG = new BinaryTreeNode('G');

    nodeA.setLeft(nodeB).setRight(nodeC);
    nodeB.setLeft(nodeD).setRight(nodeE);
    nodeC.setLeft(nodeF).setRight(nodeG);

    // In-order traversing.
    expect(nodeA.toString()).toBe('D,B,E,A,F,C,G');

    const enterNodeCallback = jest.fn();
    const leaveNodeCallback = jest.fn();

    // Traverse tree without callbacks first to check default ones.
    depthFirstSearch(nodeA);

    // Traverse tree with callbacks.
    depthFirstSearch(nodeA, {
      allowTraversal: (node, child) => {
        // Forbid traversing left part of the tree.
        return child.value !== 'B';
      },
      enterNode: enterNodeCallback,
      leaveNode: leaveNodeCallback,
    });

    expect(enterNodeCallback).toHaveBeenCalledTimes(4);
    expect(leaveNodeCallback).toHaveBeenCalledTimes(4);

    // Check node entering.
    expect(enterNodeCallback.mock.calls[0][0].value).toEqual('A');
    expect(enterNodeCallback.mock.calls[1][0].value).toEqual('C');
    expect(enterNodeCallback.mock.calls[2][0].value).toEqual('F');
    expect(enterNodeCallback.mock.calls[3][0].value).toEqual('G');

    // Check node leaving.
    expect(leaveNodeCallback.mock.calls[0][0].value).toEqual('F');
    expect(leaveNodeCallback.mock.calls[1][0].value).toEqual('G');
    expect(leaveNodeCallback.mock.calls[2][0].value).toEqual('C');
    expect(leaveNodeCallback.mock.calls[3][0].value).toEqual('A');
  });
});