# Errata: Data Structures and Algorithms Book!
**URL:** https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668
**Category:** programming
**Created:** [December 15, 2023, 3:54am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668 "2023-12-15T03:54:20Z")
**Posts on this page:** 15
**Page:** 1
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [December 15, 2023, 3:54am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/1 "2023-12-15T03:54:20Z")
This post will list all of the corrections or clarifications that have been found in the 1st edition of the Absolute Beginner鈥檚 Guide: Data Structures and Algorithms book! 馃檪
1. **[Iterative Binary Search has an undefined right variable](http://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/3)**
2. **[Recursive Binary Search Code is Missing Return Statements](http://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/4)**
3. **[Insertion Sort - Fixed undeclared j variable](http://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/5)**
4. **[LinkedList - remove and addAfter methods do not properly update the tail pointer](http://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/7)**
5. **[Binary Tree Traversal code has two mistakes.](http://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/8)**
6. **[The removeNode method in the Graph implementation has a bug where a Node removes itself.](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/13)**
---
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [December 16, 2023, 3:16am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/2 "2023-12-16T03:16:28Z")
A post was split to a new topic: [Bug in Insertion Sort Code](https://forum.kirupa.com/t/bug-in-insertion-sort-code/663699)
---
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [December 16, 2023, 2:55am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/3 "2023-12-16T02:55:38Z")
**Iterative Binary Search has an undefined right variable**
The correct version is:
```js
// 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鈥檛 defined.
---
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [December 16, 2023, 2:55am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/4 "2023-12-16T02:55:57Z")
**Recursive Binary Search Code is Missing Return Statements**
The correct version is here:
```js
// 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](http://forum.kirupa.com/t/found-a-bug-in-absolute-beginner-s-guide-to-algorithms/663637)!
---
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [December 16, 2023, 3:15am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/5 "2023-12-16T03:15:56Z")
**Insertion Sort - Fixed undeclared j variable**
The following code declares the `j` variable correctly to avoid any out-of-scope errors:
```auto
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! 馃檪
---
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [February 19, 2024, 7:05pm UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/7 "2024-02-19T19:05:58Z")
**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](https://github.com/kirupa/kirupa/blob/master/data_structures_algorithms/linkedlist.htm)
Full code pasted below:
```auto
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");
```
---
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [February 22, 2024, 6:22am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/8 "2024-02-22T06:22:06Z")
**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](http://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](https://github.com/kirupa/kirupa/blob/master/data_structures_algorithms/binary_tree_traversal.htm)
Thanks again to @timfrobisher for [pointing these two issues](http://forum.kirupa.com/t/two-bugs-in-linkedlist-data-structure-in-absolute-beginners-guide-to-algorithms/665046/5) out.
---
### Author:  [@anlexN](https://forum.kirupa.com/u/anlexN)
#### Post date: [March 10, 2025, 9:21am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/10 "2025-03-10T09:21:16Z")
Hello, I have reviewed **13. Graphs** code:
```js
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 :
```js
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?
---
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [March 10, 2025, 11:47pm UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/11 "2025-03-10T23:47:04Z")
Do you have an example where the original version doesn鈥檛 work? I spent some time trying out different Graph examples, and both your version and the book鈥檚 original version returned the same results.
You can see my file here: [kirupa/data\_structures\_algorithms/graph.htm at master 路 kirupa/kirupa 路 GitHub](https://github.com/kirupa/kirupa/blob/master/data_structures_algorithms/graph.htm)
---
### Author:  [@anlexN](https://forum.kirupa.com/u/anlexN)
#### Post date: [March 11, 2025, 8:09am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/12 "2025-03-11T08:09:26Z")
In your [kirupa/data\_structures\_algorithms/graph.htm at c23b48bcda4b8a8497139c51e709379cae54c62b 路 kirupa/kirupa 路 GitHub](https://github.com/kirupa/kirupa/blob/c23b48bcda4b8a8497139c51e709379cae54c62b/data_structures_algorithms/graph.htm#L43:)
```js
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鈥檛 see your explanation in your book.
---
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [March 11, 2025, 6:12pm UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/13 "2025-03-11T18:12:08Z")
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鈥檓 removing self-references (which don鈥檛 exist anyway). It should be as you described earlier:
```auto
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鈥檒l update the errata to call this out.
---
### Author:  [@anlexN](https://forum.kirupa.com/u/anlexN)
#### Post date: [March 12, 2025, 1:19am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/14 "2025-03-12T01:19:57Z")
when do you publish a new version book?
---
### Author:  [@kirupa](https://forum.kirupa.com/u/kirupa)
#### Post date: [March 12, 2025, 4:32am UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/15 "2025-03-12T04:32:48Z")
Likely not for another year or so. There haven鈥檛 been a whole lot of new changes since I wrote the 1st edition 馃榾
---
### Author:  [@anlexN](https://forum.kirupa.com/u/anlexN)
#### Post date: [March 13, 2025, 12:44pm UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/16 "2025-03-13T12:44:47Z")
are you still in the google company? I want to join it. Do you have recommends?
---
### Author:  [@betyek1](https://forum.kirupa.com/u/betyek1)
#### Post date: [March 13, 2025, 3:27pm UTC](https://forum.kirupa.com/t/errata-data-structures-and-algorithms-book/663668/17 "2025-03-13T15:27:57Z")
It鈥檚 great to see these corrections being documented! 馃摎