Errata: Data Structures and Algorithms Book!

programming
1

This post will list all of the corrections or clarifications that have been found in the 1st edition of the Absolute Beginner’s Guide: Data Structures and Algorithms book! :slight_smile:

  1. Iterative Binary Search has an undefined right variable

  2. Recursive Binary Search Code is Missing Return Statements

  3. Insertion Sort - Fixed undeclared j variable

  4. LinkedList - remove and addAfter methods do not properly update the tail pointer

  5. Binary Tree Traversal code has two mistakes.

2 Likes
2

A post was split to a new topic: Bug in Insertion Sort Code

3

Iterative Binary Search has an undefined right variable
The correct version is:

// Iterative Approach
function binarySearch(arr, val) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let middleIndex = Math.floor((start + end) / 2);

    if (arr[middleIndex] === val) {
      return middleIndex;
    } else if (arr[middleIndex] < val) {
      start = middleIndex + 1;
    } else {
      end = middleIndex - 1;
    }
  }

  return -1;
}

The incorrect terminating condition for the while loop had start <= right, where right wasn’t defined.

4

Recursive Binary Search Code is Missing Return Statements
The correct version is here:

// Recursive Approach
function binarySearch(arr, val, start = 0, end = arr.length - 1) {
  const middleIndex = Math.floor((start + end) / 2);

  if (val === arr[middleIndex]) {
    return middleIndex;
  }

  if (start >= end) {
    return -1;
  }

  if (val < arr[middleIndex]) {
    return binarySearch(arr, val, start, middleIndex - 1);
  } else {
    return binarySearch(arr, val, middleIndex + 1, end);
  }
}

Thanks to @transbot for noticing it and suggesting the changes!

5

Insertion Sort - Fixed undeclared j variable
The following code declares the j variable correctly to avoid any out-of-scope errors:

function insertionSort(input) {
  // Variable to store the current element being compared
  let activeNumber;

  // Loop through the array starting from the second element (index 1)
  for (let i = 1; i < input.length; i++) {
    // Store the current element in the activeNumber variable
    activeNumber = input[i];

    let j;
    
    // Inner loop to compare the activeNumber with the elements before it
    for (j = i - 1; j >= 0; j--) {
      if (input[j] > activeNumber) {
        // Move the greater element one position ahead to make space 
        // for the activeNumber
        input[j + 1] = input[j];
      } else {
        // If we find an element that is smaller than or 
        // equal to the activeNumber, exit the inner loop
        break;
      }
    }
    // Place the activeNumber in its correct sorted position
    input[j + 1] = activeNumber;
  }
}

let myinput = [24, 10, 17, 9, 5, 9, 1, 23, 300];
insertionSort(myinput);

console.log(myinput);

Thanks to @transbot for finding this one as well! :slight_smile:

7

LinkedList - remove and addAfter methods do not properly update the tail pointer

Huge thanks to @timfrobisher for pointing this out! The corrected form of this code can be seen here: kirupa/data_structures_algorithms/linkedlist.htm at master · kirupa/kirupa · GitHub

Full code pasted below:

class LinkedListNode {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  addFirst(data) {
    const newNode = new LinkedListNode(data, this.head);

    this.head = newNode;

    if (!this.tail) {
      this.tail = newNode;
    }

    this.size++;
  }

  addLast(data) {
    const newNode = new LinkedListNode(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.size++;
  }

  addBefore(beforeData, data) {
    const newNode = new LinkedListNode(data);

    if (this.size === 0) {
      this.head = newNode;
      this.size++;
      return;
    }

    if (this.head.data === beforeData) {
      newNode.next = this.head;
      this.head = newNode;
      this.size++;
      return;
    }

    let current = this.head.next;
    let prev = this.head;

    while (current) {
      if (current.data === beforeData) {
        newNode.next = current;
        prev.next = newNode;
        this.size++;
        return;
      }

      prev = current;
      current = current.next;
    }

    throw new Error(`Node with data '${beforeData}' not found in list`);
  }

  addAfter(afterData, data) {
    const newNode = new LinkedListNode(data);

    if (this.size === 0) {
      this.head = newNode;
      this.size++;
      return;
    }

    let current = this.head;

    while (current) {
      if (current.data === afterData) {
        newNode.next = current.next;

        if (current === this.tail) {
          this.tail = newNode;
        }

        current.next = newNode;
        this.size++;
        return;
      }

      current = current.next;
    }

    throw new Error(`Node with data '${afterData}' not found in list!`);
  }

  contains(data) {
    let current = this.head;

    while (current) {
      if (current.data === data) {
        return true;
      }

      current = current.next;
    }

    return false;
  }

  removeFirst() {
    if (!this.head) {
      throw new Error('List is empty');
    }

    this.head = this.head.next;
    if (!this.head) {
      this.tail = null;
    }
    this.size--;
  }

  removeLast() {
    if (!this.tail) {
      throw new Error('List is empty');
    }

    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
      this.size--;
      return;
    }

    let current = this.head;
    let prev = null;

    while (current.next) {
      prev = current;
      current = current.next;
    }

    prev.next = null;
    this.tail = prev;
    this.size--;
  }

  remove(data) {
    if (this.size === 0) {
      throw new Error("List is empty");
    }

    if (this.head.data === data) {
      this.head = this.head.next;
      this.size--;
      return;
    }

    let current = this.head;

    while (current.next) {
      if (current.next.data === data) {
        if (current.next === this.tail) {
          this.tail = current;
        }
        current.next = current.next.next;
        this.size--;
        return;
      }

      current = current.next;
    }

    throw new Error(`Node with data '${data}' not found in list!`);
  }

  toArray() {
    const arr = [];

    let current = this.head;

    while (current) {
      arr.push(current.data);
      current = current.next;
    }

    return arr;
  }

  get length() {
    return this.size;
  }
}

let letters = new LinkedList();
letters.addLast("A");
letters.addLast("B");
letters.addLast("C");
letters.addLast("D");
letters.addLast("E");

console.log(letters.toArray()); // ['A', 'B', 'C', 'D', 'E']

letters.addFirst("AA");
letters.addLast("Z");

console.log(letters.toArray()); // ['AA', 'A', 'B', 'C', 'D', 'E', 'Z']

letters.remove("C");
letters.removeFirst();
letters.removeLast();

console.log(letters.toArray()); // ['A', 'B', 'D', 'E']

letters.addAfter("D", "Q");

console.log(letters.toArray()); // ['A', 'B', 'D', 'Q', 'E']

letters.addAfter("Q", "H");
letters.addBefore("A", "5");

console.log(letters.toArray()); // ['5', 'A', 'B', 'D', 'Q', 'H', 'E']

letters.remove("E");

console.log(letters.toArray()); // ['5', 'A', 'B', 'D', 'Q', 'H']

console.log(letters.length); // 7

letters.addAfter("H", "Z");
8

Binary Tree Traversal code has two mistakes:

  1. In breadthFirstTraversal, the line observed.enqueue(root) should be discovered.enqueue(root)

  2. In depthFirstTraversal, if you are using the Stack implementation from the book as opposed to including the one from kirupa.com, you will be missing the length method.

Both of these issues are fixed in the version of the full example shared here: kirupa/data_structures_algorithms/binary_tree_traversal.htm at master · kirupa/kirupa · GitHub

Thanks again to @timfrobisher for pointing these two issues out.