Graph

Question 1

What is a graph?

Answer 1

A graph is a collection of nodes and any edges between those nodes.

Question 2

Linked List

Answer 2

A Linked List data structure represents a linear sequence of “vertices” (or “nodes”), and tracks three important properties:
head The first node in the list.
tail The last node in the list.
length The number of nodes in the list; the list’s length.

Linked List Node Properties:
value The actual value this node represents.
next The next node in the list (relative to this node).
previous The previous node in the list (relative to this node).

Unlike Arrays, Linked Lists contain non-contiguous data. Though Linked Lists represent data that is ordered linearly, that mental model is just that - an interpretation of the representation of information, not reality.

In reality, in the actual hardware of your machine, whether it be in disk or in memory, a Linked List’s Nodes are not stored in a single continuous block of addresses. Rather, Linked List Nodes live at randomly distributed addresses throughout your machine! The only reason we know which node comes next in the list is because we’ve assigned its reference to the current node’s next pointer.

Time/Time/Space
Access	Θ(n)	O(n)	O(n)
Search	Θ(n)	O(n)	O(n)
Insertion	Θ(1)	O(1)	O(n)
Deletion	Θ(1)	O(1)	O(n)

Question 3

What is a tree?

Answer 3

A Tree is a Graph that does not contain any cycles.

Question 4

What is a binary tree?

Answer 4

A Binary Tree is a Tree where nodes have at most 2 children.

Question 5

Basic Tree Terminology

Answer 5

tree - graph with no cycles
binary tree - tree where nodes have at most 2 nodes
root - the ultimate parent, the single node of a tree that can access every other node through edges; by definition the root will not have a parent
internal node - a node that has children
leaf - a node that does not have any children
path - a series of nodes that can be traveled through edges - for example A, B, E is a path through the above tree

Question 6

Breadth-first search

Answer 6

Trees can also be traversed level-by-level, where you visit every node on a level before going to a lower level. This search is referred to as breadth-first search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth.

Question 7

Depth-first searches

Answer 7

Pre-order traversal
In the above image, the pre-order is noted by when the dotted line touches the red dot and yields F, B, A, D, C, E, G, I, H. The algorithm is as follows and is “pre-order” because you access the value of the node before recursively descending.

Access the data of the current node
Recursively visit the left sub tree
Recursively visit the right sub tree

In-order traversal
In the above image, the in-order is noted by when the dotted line touches the yellow dot and yields A, B, C, D, E, F, G, H, I. The algorithm is as follows and is “in-order” because you access the value of the node after descending to the left but before descending to the right.

Recursively visit the left sub tree
Access the data of the current node
Recursively visit the right sub tree

Post-order traversal
In the above image, the post-order is noted by when the dotted line touches the green dot and yields A, C, E, D, B, H, I, G, F. The algorithm is as follows and is “post-order” because you access the value of the node after descending to both branches.

Recursively visit the left sub tree
Recursively visit the right sub tree
Access the data of the current node

Question 8

Binary Search Tree (BST)

Answer 8

given any node of the tree, the values in the left subtree must all be strictly less than the given node’s value.
and the values in the right subtree must all be greater than or equal to the given node’s value

In a binary search tree, in-order traversal retrieves the keys in ascending sorted order.

Question 9

Graph Implemetations

Answer 9

GraphNode Class
This implementation is most similar to how we implemented binary trees. That is, we create a node class that maintains a value and an array of references to neighboring nodes. This easily solves the problem that a node can have any number of neighbors, no longer just a left and right.

Adjacency Matrix
This is the often the mathematician’s preferred way of representing a graph. We use a 2D array to represent edges. We’ll first map each node’s value to an index. This means A -> 0, B -> 1, C -> 2, etc.. Below is the mapping for Graph 3:

Adjacency List
An adjacency list seeks to solve the shortcomings of the matrix implementation. We use an object where keys represent the node labels. The values associated with the keys will be an array containing all adjacent nodes:
An adjacency list is easy to implement and allows us to refer to the entire graph by simply referencing the object. The space required for an adjacency list is the number of edges in the graph.