# Block 7: Trees and graphs

The flashcards below were created by user ccc on FreezingBlue Flashcards.

1. Draw a complete binary search tree containing 1,2,3,4,5 and 6.
2. Here is an adjacency matrix for a weighted directed graph. Cells contain weights
of edges, empty cells mean there is no edge. Complete the drawing of the graph to
the right by adding directed edges and weights.
3. In the same graph as B), one path from A to E is A→C→E, with a combined
weight of 9.
Write three other paths from A to E, and the combined weight of each.
• A → D → E (11)
• A → B → C → E (9)
• A → C → D → E (15)
4. If a multigraph has E edges, what is the maximal/minimal number of nodes it may have? Answer in O notation. Assume the graph is undirected and connected (no unreachable nodes).
Maximal N = E+1 , O(E)

Minimal N = 1, O(E)
5. Given this weighted directed graph, we use Dijkstras Algorithm (3 points)
to find the shortest path from A to all other (reachable) nodes. Write the nodes it
reaches and the length of the shortest path it finds for each. Write them in the
order that the algorithm would find them.
• B 2
• D 3
• C 4
• F 5
6. List the Nodes of the same graph in breadth
first order starting from E. (2 points)
E,D,C,F,B
7. ) In an adjacency matrix for the same graph, where each cell has either a weight
or -1 if there is no edge, how many cells would have -1 in them? Also write a
formula for calculating this number for any graph, in terms of number of nodes N
and number of edges E.

• 6 * 6 - 9 = 27
• N^2 - E
8. If a binary tree has N nodes, what is the maximal/minimal height the tree may
have (you may answer in O notation)
Maximal H = N-1 , O(N)

Minimal H = O( log(N) )
9. If a graph has E edges, what is the maximal/minimal number of nodes it may
have? Answer in O notation. Assume the graph is undirected, connected (no
unreachable nodes) and not a multigraph.
Maximal N = O(E)

Minimal N = O( sqrt(E) ) [E=n^2]
10. A directed weighted graph is represented as an adjacency matrix g, such that g[i][j]
is a boolean that is true if and only if there is an edge from node i to node j.
A) Write the body of the method:
public static int highestDegree(boolean[][] g)
That computes the highest number of outgoing edges of any node.
• int size = g.length;
• int top = 0;

• for (int i = 0;i<size;i++) {
• int deg = 0;
• for (int j = 0;j<size;j++) {
• if (g[i][j]) deg++;

• if (deg>top) top=deg;
• }