Trees and Graphs

Question 1

Tree

Answer 1

a data structure composed of nodes. It’s actually a special kind of graph.

The best way to understand a tree is with a recursive explanation

• In the data structure, each tree has a root note
• Root node has 0+ child nodes
• Each child node has 0+ child nodes
• etc.

Provides fun stuff like log(n) search & insertion. Also able to store many combinations (like a dictionary) in less space and with some benefits than just storing the whole thing (see Tries and prefix matches)

Question 2

Basic Tree Node Definition

Answer 2

TreeNode:
val (any type)
children (list of TreeNode)

Question 3

Binary Tree

Answer 3

A tree with up to 2 children

Question 4

Binary Tree vs Binary Search Tree

Answer 4

BST has an ordering property: all left decedents <= n. All right decedents > n

Question 5

Balanced vs Unbalanced

Answer 5

For practical uses, this usually means “just balanced enough to ensure log(n) insert and find.

Common balanced trees are red-black trees and AVL trees

Question 6

Complete Binary Tree

Answer 6

All levels are filled in except for the last level, which must be filled in from left-to-right with no gaps.

Question 7

Full Binary Tree

Answer 7

Every node has zero or two children

Question 8

Perfect Binary Tree

Answer 8

Both Full and Complete. It has 2^k - 1 nodes where k is the number of levels

Question 9

Common Traversals

Answer 9

in-order: current in between children, visits nodes in ascending order (left, node, right)
pre-order: current before children (node, left, right)
post-order: current after children (left, right, node)

Question 10

Binary Heap

Answer 10

Most commonly min-heaps and max-heaps. These are COMPLETE trees where the root element is either the min or max element.

MinHeap supports log(n) insert, remove, deleteMin and constant time getMin without additional memory overhead. Each node’s children are larger than it.

Key Operations: insert and extractMin

There are ways to implement min element-type structures using queues, for example, but some of the operations either take a performance hit (e.g. linear), or require more space to store.

Question 11

Insert to MinHeap

Answer 11

Insert to bottom of tree then percolate up. O(log n) time where n is the number of nodes in the heap.

Question 12

Extract Minimum Element from MinHeap

Answer 12

Remove the minimum element and swap in the very last element in the heap (bottom, right-most element). Then percolate down.

Question 13

Trie (Prefix Trees)

Answer 13

Commonly used to represent the entire (English) language for quick prefix lookups.

A Trie is a special application of an n-ary tree used to represent prefixes and complete words.

A node in a trie can have 0 to ALPHABET_SIZE + 1 children

The root of the tree does not have any value. The children represent letters or may have either a boolean or node value like ‘ * ‘ indicating that the previous path represents a complete word.

A trie can check if a string is a valid prefix in O(K) time, where K is the length of the string.

Question 14

Trie vs Hash Map for prefix lookup

Answer 14

Both require O(K) time, but hash map requires more space than a Trie.

TODO: exact space comparison between Trie and Hash Map for prefix lookup

Question 15

Graphs

Answer 15

Collection of nodes with edges between some of them

Question 16

Directed Graph

Answer 16

Nodes are connected by unidirectional edges

Question 17

Undirected Graph

Answer 17

Nodes are connected by bidirectional edges

Question 18

Connected Graph

Answer 18

There exists a path from any vertex to any other vertex

Question 19

Cycle (in a graph)

Answer 19

Starting at node A, there exists a path through other nodes back to A.

In an undirected graph, you may not visit the node you just visited to detect a cycle. In other words, the minimum number of nodes in an undirected cycle is 3. The minimum number of nodes in a directed cycle is 1 (self-loop).

Terminology: “cyclic graph” vs “acyclic graph”

Question 20

Complete Graph

Answer 20

a graph in which each pair of graph vertices is connected by an edge

Sometimes called “universal graph” in older literature

Question 21

Representing a graph in programming

Answer 21

There are 2 common ways:

1. Adjacency List
2. Adjacency Matrix

Question 22

Adjacency List

Answer 22

Every vertex stores a list of adjacent vertices.

In an undirected graph, an edge like (a, b) would be stored twice: once in a’s adjacent vertices and once in b’s adjacent vertices.

Most common way to represent a graph.

class Graph:
  list(nodes) [type: Node]

class Node:
  name [type: Str]
  list(children) [type: Node]

Additional classes are not necessary to represent a graph. An array (or hash table) of lists can store the adjacency list. More compact but not as clean as using node classes.

Question 23

Why is a Graph Unlike a Tree?

Answer 23

You can’t necessarily reach all the nodes from a single node.

Question 24

Common Graph Search

Answer 24

DFS & BFS

Question 25

Common scenarios for graph DFS

Answer 25

Often preferred for visiting every node in the graph (simpler)

Question 26

Common scenarios for graph BFS

Answer 26

Often preferred for (shortest) path

Question 27

Graph DFS Implementation

Answer 27

Either have a visited set or visited attribute on the node itself.

For a connected graph, start with a root. then search each of its adjacent nodes.

If the graph is not connected, we’ll need a mechanism to pick a new root. Perhaps use a hash set of all nodes. If one is visited, remove from the hash set of “not-visited”

Question 28

Graph BFS Implementation

Answer 28

NOT recursive. Uses a queue. (usually best)

Mark the root, and enqueue. Do not enqueue an already marked node. It hasn’t yet been visited, but it’s been “marked” because it’s been inserted into the queue.

Question 29

Graph Bidirectional Search

Answer 29

Find shortest path between a source and destination node. Essentially 2 simultaneous BFS searches. We’ve found a path once the searches collide.

This is because, if we have a path of length (depth) d, each of our searches only need to check d/2 levels. Since exploring each depth is exponential, we would have had to search k^d nodes, but instead we only need to search 2k^(d/2) nodes

Faster than normal BFS by a factor of K^(d/2) where k is the maximum number of adjacent nodes from any node.

Question 30

Topological Sort

Answer 30

todo

Question 31

Dijkstra’s Algorithm

Answer 31

todo

Question 32

AVL Trees

Answer 32

todo

Question 33

Red-Black Trees

Answer 33

wishlist?

Question 34

Adjacency Matrices

Answer 34

A common way to represent a graph.

• NxN boolean matrix (N is the number of nodes)
• matrix[i][j] == true => ∃ edge from node i to node j (i.e. from ROW to COL)
• matrix is symmetric in undirected graphs

Can perform the same algorithms used on adjacency lists (e.g. BFS), but they’re somewhat less efficient since at each node, you don’t have direct access to all neighbors. In adjacency matrix, iteration will be O(NxN) as opposed to O(N) (yes?)

TODO: when are adjacency matrices used then?