# Errata: Data Structures and Algorithms Book!

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!

2 Likes

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

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.

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!

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!

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;
}
}

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

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

this.size++;
}

this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}

this.size++;
}

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

this.size++;
return;
}

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

prev = current;
current = current.next;
}

}

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

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;
}

}

contains(data) {

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

current = current.next;
}

return false;
}

removeFirst() {
throw new Error('List is empty');
}

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

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

this.tail = null;
this.size--;
return;
}

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");
}

this.size--;
return;
}

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;
}

}

toArray() {
const arr = [];

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

return arr;
}

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

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

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']

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

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

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.