Creating this topic to catch any typos and bugs in the 4th Edition of Data Structures & Algorithms in Swift.
1 Like
How do I fix this error? Why doesn’t example work for this and the Previous chapter?:
error: Node.playground:24:1: error: cannot find ‘example’ in scope
example(of: “creating and linking nodes”) {
^~~~~~~
Regarding the Performance Analysis section for removing elements of a LinkedList… Shouldn’t removeLast() be O(n) and not O(1)? Since the implementation of removeLast() involves iterating over every node in the list starting at the head?
2 Likes
Chapter 36: Graph
Why AdjancencyList and Matrix is a class and not struct in the book?
public class AdjacencyList<T: Hashable>: Graph {
private var adjacencies: [Vertex: [Edge]] = [:]
public init() {}
// more to come …
}
What are the advantage of this? and what is wrong if we make it struct?
Yes, that’s correct. The most recent version of the book states that:
removeLastrequires you to traverse all the way down the list. This makes for an O(n) operation, which is relatively expensive.
https://www.raywenderlich.com/books/data-structures-algorithms-in-swift/v4.0/chapters/6-linked-lists
1 Like
Chapter 22, page 229 (Pdf version), removing the root node from the heap. “A remove operation will remove the maximum value at the root node. To do so, you must first swap the root node with the last element in the heap.” : In the diagram on page 228, the maximum value is “10” and the last node is “3”, on page 229 the lefthand diagram at the top of the page has swapped “10” with “7”. There was no “7”. In the immediate diagram to the right at the top of the page, the “7” has turned into a “3”.
1 Like
Chapter 36: Graphs. Page 338 and 339 (PDF version). Error in the adjacency list diagram on page 339. For the “Tokyo” vertex, the adjacency list has two “Detroit”, missing “Kong Kong” in place of a “Detroit”.
Thank you for taking time to report these! We will get them updated for the next edition!
I think I found a contradiction in the Binary Search Tree definitions in Chapter 14 and Chapter 15.
Chapter 14 Binary Search Tree says:
- The value of a left child must be less than the value of its parent.
- Consequently, the value of a right child must be greater than or equal to the value of its parent.
But Chapter 15 Binary Search Tree Challenges in “Solution to Challenge 1” says:
A binary search tree is a tree where every left child is less than or equal to its parent, and every right child is greater than its parent.
So chapter 14 says that values equal to the parent should be on the right side but chapter 15 says that they should be on the left side. I think the issue is that there is no universally agreed upon definition of a BST. Some implementations allow duplicates and some do not. When they do allow duplicates, there’s no agreement as to what branch a duplicate should go under. But it would still be helpful for the book to have one consistent definition on this matter.
Are you kidding me that no one has answered this question? The examples do NOT WORK directly from source and this basic question is being ignored? Really?
Hi! I guess the table below, summarizing complexity is still wrong
Page 67 - Chapter 6 - LInkedList - v4.0
removeLast should be O(n) and not O(1).
1 Like
This function is wrong, because it iterate recursively on tree (the global variable) and not on node (the input one).
The right function should be
func height<T>(of node: BinaryNode<T>?) -> Int {
// 1
guard node != nil else {
return -1
}
// 2
return 1 + max(height(of: node?.leftChild), height(of:node?.rightChild))
}
Chapter 13 - page 150
Chapter 13 - page 152 is missing the empty check for the array in deserialize
Chapter 21, Binary Search Challenges
Challenge #2 Solution shows “An unoptimized but elegant solution” that “is quite simple”.
It is however wrong.
The solution returns the range
firstIndex(of:)..<lastIndex(of:)
while in fact it should return the range
firstIndex(of:)..<(lastIndex(of:) + 1)
so that the last index is also included in the half-open interval
In the LinkedList chapter, under the section for removing values, it says there are three operations: 1. pop
removeLast
remove(at:)
In the actual body of the text, the operation discussed is remove(after:)
1 Like
The adjacency list and matrix are nicely explained in kuickcode dot com
List<int[]>[] graph = new List[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < edges.length; i++) {
int[] edge = edges[i];
int u = edge[0];
int v = edge[1];
int w = distance[i];
//If there is an undirected edge from vertex u to vertex v, then we need install v as child of u and vice versa.
graph[u].add(new int[]{v, w});
graph[v].add(new int[]{u, w});extra line
//Code for Adjacency List for directed & undirected graph are same except for above extra line
}
Correct a Binary Tree
You have a binary tree with a small defect. There is exactly one invalid node where its right child
incorrectly points to another node at the same depth but to the invalid node’s right.
Given the root of the binary tree with this defect, root, return the root of the binary tree after removing this invalid node and every node underneath it (minus the node it incorrectly points to).
INPUT:
Found this problem in kuickcode dot com