Height of a tree (or a node) is the longest path from the root (or from the node) to a
leaf node
4
New cards
For BST: height = max (? ) + 1
left child’s height , right child’s height
5
New cards
The height of a NULL node is
\-1
6
New cards
leaf nodes have height
0
7
New cards
Use ? to determine if trees are imbalanced
balance factor
8
New cards
balance factor formula
hleft - hright
9
New cards
trees of both height can differ by
1
10
New cards
\-ve balance factor = right-heavy tree = rotate ?
left
11
New cards
\+ve balance factor = ? = rotate right
left heavy tree
12
New cards
AVL trees have what guaranteed time for all operations
o(logn)
13
New cards
For N nodes =
N-1 edges (parent child relation)
14
New cards
all nodes are accessible through?
root
15
New cards
There is only one path to reach any node from?
root
16
New cards
Trees are a special form of
graphs
17
New cards
Edges can connect any vertex in any possible way
any possible way
18
New cards
Any vertex can be accessed through
any path
19
New cards
A graph is a way of representing relationships that exist between
pairs of objects
20
New cards
A Graph G can be represented as an ordered pair of a set V of vertices and a set E of ?
edges
21
New cards
Edges in graphs can be directed or
undirected
22
New cards
Adjacent Vertices: Two vertices, u and v, connected together via the same ?
edge
23
New cards
An edge is said to be ? to a vertex if the vertex is one of the edge’s endpoint
incident
24
New cards
A ? is a sequence of alternating vertices and edges that starts at a vertex and ends at a ? such that each edge is incident to its predecessor and ? vertex.
path, vertex, successor
25
New cards
Cycle is a path that starts and ends at the same
vertex and includes at least one edge
26
New cards
Undirected Graphs: Edges do not have a ?
direction
27
New cards
Undirected Graphs: Edge (u, v) will be equivalent to the edge ?
(v, u)
28
New cards
Directed Graphs or Digraphs: Edges have a direction pointing from
one vertex to another vertex
29
New cards
Mixed Graphs: Edges have a direction pointing from one vertex to another vertex and some edges are undirected
one vertex to another vertex
30
New cards
Directed Acyclic Graphs: Finite directed graph with no
cycles
31
New cards
Complete Graphs: All vertices are connected to
each other
32
New cards
Unweighted graphs: all edges are of equal weight of
1
33
New cards
Weighted graphs: have different values associated to ?
edges
34
New cards
What is the order that Breadth-First Search (BFS) goes by to visit nodes/vertices
starts from top of height all the way to leafs by row
35
New cards
What is the order that Depth-First Search (DFS) goes by to visit nodes/vertices
starts from left side all the way down to leaf then middle, then right side down to leaf
36
New cards
Time complexity of Breadth-First Search (BFS) ?
O(V+E)
37
New cards
BFS Memory complexity is not good bc it stores many references so ? is usually preferred
DFS
38
New cards
DFS constructs a ? for unweighted graphs (smaller number of edges)
\
Shortest path
39
New cards
DFS uses ?
stack LIFO
40
New cards
BFS uses ?
queue FIFO
41
New cards
Vertex is a
node
42
New cards
edge
lines that connect nodes
43
New cards
time complexity for DFS
o(v+e)
44
New cards
DFS is used to solve
mazes
45
New cards
BFS Walk through all nodes on the same ?
level
46
New cards
BFS is based on
queues
47
New cards
BFS is suitable for searching nearby
vertices
48
New cards
BFS has no concept of
backtracking
49
New cards
DFS goes as deep as possible until there is ?
no neighbor left
50
New cards
DFS is based on
stacks
51
New cards
Suitable for searching vertices farther away from
the source
52
New cards
DFS can recursively ?
backtrack
53
New cards
On what side is the predeccor?
left
54
New cards
on what side is the successor ?
right
55
New cards
if you delete a root node what will be the new root? Predecessor or Successor?
predecessor, largest item in right subtree
56
New cards
Pre-order traversal Visit root node first, then
left-subtree and finally right-subtree
57
New cards
Post-order traversal Visit left-subtree first, then
right-subtree, and finally the root node
58
New cards
In-order traversal Visit left-subtree first, then
root node, and finally right-subtree
59
New cards
what is the pre order traversal
32,10,1,19,16,23,55,79
60
New cards
what is the post order traversal
1,16,23,19,10,79,55,32
61
New cards
what is the in order traversal
1,10,16,19,23,32,55,79
62
New cards
stack all operation time
o(1)
63
New cards
queue: dequeue operation time
o(n)
64
New cards
linked list operation time to remove tail element
o(n)
65
New cards
doubly linked list time operation
o(1)
66
New cards
hash tables time operation to locate bucket
o(1)
67
New cards
hash tables time operation to locate element
o(n)
68
New cards
Each element in a tree has a parent element and children
zero/more
69
New cards
Edge: Connection between ? nodes to show a relationship between them
2
70
New cards
Path: A path is an ordered list of nodes that are connected by ?(from top to bottom)
edges
71
New cards
Height of a node x: number of edges in **longest** path from the **node** x to a ?
leaf
72
New cards
Depth/Level of node x: **Number** of **edges** in path from ? to **node** x
root
73
New cards
Degree of a **node**: The number of its ?
children
74
New cards
Degree of a **tree**: Total number of ? in it
nodes
75
New cards
In a tree, there must only be a ? path from the root node to any other node
single
76
New cards
Every node in the tree can have at most ? children (left child and right child)
2
77
New cards
balanced BST time
o(logn)
78
New cards
imbalanced BST time
o(n)
79
New cards
mapping can be defined as an association between
2 objects
80
New cards
mapping associated objects can be referred as
key value pairs
81
New cards
array of key-value pairs are sometimes referred as
associative arrays or maps
82
New cards
Unlike a standard array, indices for a map need not be
consecutive nor even numeric.
83
New cards
Unlike Python, many other programming languages ? have a built-in mapping data type like dictionary
do not
84
New cards
Elements are stored as ? in the list
objects
85
New cards
Searching a particular key requires ? time complexity
o(n)
86
New cards
How does the dictionary have o(1) time complexity for all operations? Python Dictionary is implemented with another?
data structure
87
New cards
• We can pass any “?”of key into a mechanism to convert it into indices/codes
type
88
New cards
The goal of a hash function, h, is to map each key, k, to an integer in the range \[?\]
\[0, N - 1\]
89
New cards
N in \[0, N - 1\] is the ?
capacity of a hash table
90
New cards
what is the value of “Tim” in the map, M, containing N=11 memory locations?
1
91
New cards
Ali = ? % 11
3
92
New cards
Sue = ? % 11
4
93
New cards
Mia = ? % 11
4
94
New cards
if N=11 memory locations what is the last value of the index
10
95
New cards
We can store multiple items in any
specific bucket
96
New cards
what is a bucket in code
M\[j\]
97
New cards
M is the ? of buckets
array
98
New cards
j is the
index generated by hash function
99
New cards
Time to search for the bucket is
O(1)
100
New cards
Time to search a key in the bucket depends on the size of the bucket. So for size m time complexity is