Data Structures Flashcards
What is a graph
Any collection of nodes and their pointers to other nodes. Linked lists and trees are both types of graphs
What is a binary tree
A binary tree is a type of tree. It is a collection of nodes. Every node has between 0 to 2 children, and every node except the root has exactly one parent.
In a tree, what is a root node
The root node is the node at the “top” of the tree. Every node in the tree is accessible starting from the root node. The root node has no parents
In a tree, what is a parent and what is a child
If you have a node A with an edge to a node B, so A -> B, we call A the parent of node B, and node B a child of node A.
In a tree, what is a leaf node
A leaf node is a node that has no children
In a tree, what is the depth of a node
The depth of a node is how far it is from the root node. The root has a depth of 0. Every child has a depth of parentsDepth + 1, so the root’s children have a depth of 1, their children have a depth of 2, and so on.
in a tree, what is a subtree
A subtree of a tree is a node and all of it’s descendants. A subtree is a valid tree where the chose node is the root of the subtree
What are the advantages/disadvantages of DFS vs BFS
DFS can waste a lot of time if the value you are searching for is on the side which you are searching second
BFS can waste a lot of time if your values are in leaf nodes
Space complexity for a perfect binary tree in DFS is O(log n) while, for a BFS it is O(n)
For a lopsided tree, like a line, DFS space complexity will be O(n) and BFS will be O(1)
Define a Binary Search Tree (BST)
A BST is a binary tree, for each node the value of the node is greater than all of the values of the left children and less than all of the values of the right children
Operations like searching, adding, and removing can all be done in O(log n)
What traversal will handle the nodes of a binary search tree in sorted order
in-order left -> right
In a graph, what does it mean to have directed edges
Directed edges mean you can only traverse in one direction
In a graph, what does it mean to have undirected edges
Undirected edges mean you can traverse in both directions
In a graph, what is a connected component
A connected component is a group of nodes that are connected by edges
In a graph, what is a node’s indegree
A nodes indegree is the number of edges that can be used to reach a node
In a graph, what is a node’s outdegree
A nodes outdegree is the number of edges that can be used to leave a node
In a graph, what is a neighbor
Neighbors are nodes connected by an edge. In the graph A <-> B <-> C, A is neighbors with B, B is neighbors with A and C, and C is neighbors with B
In the context of a graph, what is an adjacency list
- A list of vertices where each vertex has a list of neighboring vertices
- In python, you can use the
defaultdict(list)to hold and adjacency list
0->[1,2] 1->[2,3] 2->[3]
In the context of a graph, what is an adjacency matrix
- A matrix that is used to represent adjacent vertices
- A row represents a vertex and it’s columns represents if the vertex has an edge between the corresponding vertex
In the context of a graph, what is an array of edges
- An array of pairs of vertices that are connected by an edge
[[0,1], [1,2], [0,3]]
In the context of a graph, what is a matrix
- A mxn coordinate system
- Generally this is represented as a 2-D array
What is a greedy algorithm
- An algorithm that makes a locally optimal decision at every step
- Most greedy problems are looking for a maximum or minimum
- Sorting is the most common algorithm associated with greedy algorithms
What is a trie or prefix trie
- A trie is graph that stores characters at each node
- It can be used to efficiently implement string searching/matching patterns
