### List:
	node1 -> node2 -> node3

### Tree:
	node1 -> node2
		  -> node3
		  -> node4

### Binary Trees:
	node1 -> left_node (child)
		  -> right_node (child)

``` C
typedef struct nodeBtree {
	int data;
	struct nodeBtree *left;
	struct nodeBtree *right;
} Node;
```

The top most node of a tree is called the root node.
Nodes at the same height in the tree are said to be in the same level in the tree: level 0, level 1, ...
Nodes with no children nodes are called leaf nodes.

### Binary Search Tree (BST):
- A tree such that at every node, if a value (key) is <= value (key) in the node, then that key must be stored somewhere on the left sub-tree
  otherwise, store in the right sub-tree

- On average, BST search is O(log2 N).

- BST insert (key, root):
	- if root is NULL, new node becomes root
	- else compare key against root -> key
		if less or equal, insert(key, +/- -> left)
		else insert(key, root -> right)

- if BST is fully packed, every single level, except for the last level are fully filled in.
- a full BST can hold up to N keys in a tree of height O(log2 N) -- every level duplicates the capacity of the BST
- when do I expect close to packed BST full? If keys in random order
- when the keys are sorted, O(N)
- with the key, we want to unqiuely identify each node


### BST Delete
- node w/ no children:
	- search: find the node with the key to delete
		- set parent link to NULL
		- free the node
- node with 1 child:
	- search:
		- link parent node to granchild node
		- free the node
- node with 2 child:
	- search:
		- promote smallest key on the right side
		- delete the old node for the smallest key (hold on to the reference after promoting)
		OR
		- promote the largest key on the left side
		- delete the old node for the largest key (hold on to the reference after promoting)


### BST Traversal
- in-order traversal: left, then middle, then right to produce an ascending order list of keys -- reverse order if you want descending order
	- algorithm:
		- do in-order traversal of left node
		- apply operation on this node, i.e. print() -- print value of all nodes
		- do in-order traversal of of right sub-tree
	- order of complexity: Traversal (in-order) on average -> O(N) + Building BST: insert() -> O(N log N)
- pre-order traversal:
	- algorithm:
		- apply operation to middle node
		- pre-order traversal on left sub tree
		- pre-order traversal on right sub tree
	- you preserve the order of the BST when you copy it
	- order of complexity: compilers and NLP
- post-order traversal:
	- algorithm:
		- post-order traversal left sub tree
		- post-order traversal right sub tree
		- apply operation to middle node
	- Delete BST application
	- Just a traversal, you get a free step since you delete as you go and never touch the node again, O(N)

**********************

# Graphs & Recursion

### Graph -> Set of Nodes/Vertices (V)
- represents data in your collection
	- Nodes: represented with a circle w/ an index and a bunch of data
	- Edges: connections between nodes - represent relationship between data items

### Types of Graphs:
- Undirected graph: social networks like facebook
	- relationship is both-ways
- Directed graphs:
	- hierarchical relationship
	- no link backs, one way


### Neighbourhood of a node:
- nodes connected to 'this' one
- out-neighbourhood: edges from 'this' node to others
- in-neighbourhood: edges arriving at 'this' node

- who are neighbours? who are my neighbours' neighbours?
- degree: # of nodes in the neighbourhood
	- out-degree: children in geneology
	- in-degree: parents in geneology

### Path:
- through a graph, a series or sequence of nodes that are visited from the start node to an end node

### Cycle:
- in a path... a path with at least 3 nodes that starts and ends at the same node for unidrected graphs
- in a directed graph, the minimum number of nodes is 1.

### Graph Representation:
- need to store V: LL, BST, array
- ways to store edges:
	- option A: Adjacency list (storing E)
		- Array of one entry per node
		- Each entry has a pointer to a linked list of connections
		- For directed graphs, if node A and B are connected, you will find entries of each other in their edge list
		- Edge query is O(N)
	- option B: Adjecency Matrix
		- Array of arrays, n x n matrix
		- 0 or 1 depending on whether the nodes are connected or not
		- Edge query O(1)