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! 
3 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;
}
}
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");
Binary Tree Traversal code has two mistakes:
-
In
breadthFirstTraversal, the lineobserved.enqueue(root)should bediscovered.enqueue(root) -
In
depthFirstTraversal, if you are using theStackimplementation from the book as opposed to including the one from kirupa.com, you will be missing thelengthmethod.
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.
Hello, I have reviewed 13. Graphs code:
class Graph {
constructor() {
// Map to store nodes and their adjacent nodes
this.nodes = new Map();
// Flag to indicate if the graph is directed or undirected
this.isDirected = false;
}
// Add a new node to the graph
addNode(node) {
if (!this.nodes.has(node)) {
this.nodes.set(node, new Set());
}
}
// Add an edge between two nodes
addEdge(node1, node2) {
// Check if the nodes exist
if (!this.nodes.has(node1) || !this.nodes.has(node2)) {
throw new Error('Nodes do not exist in the graph.');
}
// Add edge between node1 and node2
this.nodes.get(node1).add(node2);
// If the graph is undirected, add edge in
// the opposite direction as well
if (!this.isDirected) {
this.nodes.get(node2).add(node1);
}
}
// Remove a node and all its incident edges from the graph
removeNode(node) {
if (this.nodes.has(node)) {
// Remove the node and its edges from the graph
this.nodes.delete(node);
// Remove any incident edges in other nodes
for (const [node, adjacentNodes] of this.nodes) {
adjacentNodes.delete(node);
}
}
}
// Remove an edge between two nodes
removeEdge(node1, node2) {
if (this.nodes.has(node1) && this.nodes.has(node2)) {
// Remove edge between node1 and node2
this.nodes.get(node1).delete(node2);
// If the graph is undirected, remove edge
// in the opposite direction as well
if (!this.isDirected) {
this.nodes.get(node2).delete(node1);
}
}
}
// Check if an edge exists between two nodes
hasEdge(node1, node2) {
if (this.nodes.has(node1) && this.nodes.has(node2)) {
return this.nodes.get(node1).has(node2);
}
return false;
}
// Get the adjacent nodes of a given node
getNeighbors(node) {
if (this.nodes.has(node)) {
return Array.from(this.nodes.get(node));
}
return [];
}
// Get all nodes in the graph
getAllNodes() {
return Array.from(this.nodes.keys());
}
// Set the graph as directed
setDirected() {
this.isDirected = true;
}
// Set the graph as undirected
setUndirected() {
this.isDirected = false;
}
// Check if the graph is directed
isGraphDirected() {
return this.isDirected;
}
}
I think removeNode function is wrong, it should be rewrited to :
removeNode(nodeToRemove) {
if (this.nodes.has(nodeToRemove)) {
// Remove the node and its edges from the graph
this.nodes.delete(nodeToRemove);
// Remove any incident edges in other nodes
for (const [node, adjacentNodes] of this.nodes) {
adjacentNodes.delete(nodeToRemove); // Use nodeToRemove here
}
}
}
Do you think so?
1 Like
Do you have an example where the original version doesn’t work? I spent some time trying out different Graph examples, and both your version and the book’s original version returned the same results.
You can see my file here: kirupa/data_structures_algorithms/graph.htm at master · kirupa/kirupa · GitHub
removeNode(nodeToRemove) {
if (this.nodes.has(nodeToRemove)) {
// Remove the node and its edges from the graph
this.nodes.delete(nodeToRemove);
// Remove any incident edges in other nodes
for (const [node, adjacentNodes] of this.nodes) {
adjacentNodes.delete(node);
}
}
}
why does adjacentNodes contain node? node can go to itself? node by itself have cycle? I don’t see your explanation in your book.
Hi @anlexN - you are right. It required me to sleep and wake up today and see it with a fresher perspective 
In what I had originally, instead of removing references to the deleted node, I’m removing self-references (which don’t exist anyway). It should be as you described earlier:
removeNode(nodeToRemove) {
if (this.nodes.has(nodeToRemove)) {
// Remove the node and its edges from the graph
this.nodes.delete(nodeToRemove);
// Remove any incident edges in other nodes
for (const [node, adjacentNodes] of this.nodes) {
adjacentNodes.delete(nodeToRemove); // Now properly removing nodeToRemove
}
}
}
Thanks for flagging this. I’ll update the errata to call this out.
when do you publish a new version book?
Likely not for another year or so. There haven’t been a whole lot of new changes since I wrote the 1st edition 
are you still in the google company? I want to join it. Do you have recommends?
It’s great to see these corrections being documented! 
