Self-Assessment Quiz: Trees

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

A tree is defined as a graph that is:

A) connected and may contain cycles B) connected and acyclic C) acyclic but possibly disconnected D) any graph with $n - 1$ edges

Question 2

A tree has 23 vertices. Exactly how many edges does it have?

A) 22 B) 23 C) 24 D) cannot be determined without more information

Question 3

Which of the following is not an equivalent characterization of a tree (Theorem 31.1)?

A) there is exactly one path between every pair of vertices B) it is connected, and removing any edge disconnects it C) it is acyclic, and adding any edge between non-adjacent vertices creates a cycle D) every vertex has degree at most 2

Question 4

In a rooted tree, the depth of a vertex is measured:

A) up from the deepest leaf B) down from the root (the root has depth 0) C) as the number of its children D) as the number of its descendants

Question 5

The height of a rooted tree equals:

A) the number of leaves B) the depth of the root C) the maximum depth over all vertices D) the number of internal nodes

Question 6

Which traversal of a binary search tree visits the keys in sorted (increasing) order?

A) preorder B) inorder C) postorder D) level-order

Question 7

You want to free (deallocate) every node of a binary tree in C. Which traversal must you use?

A) preorder B) inorder C) postorder D) any order works

Question 8

For the binary tree Node(1, Node(2), Node(3)), the preorder traversal is:

A) $[2, 1, 3]$ B) $[1, 2, 3]$ C) $[2, 3, 1]$ D) $[3, 2, 1]$

Question 9

A binary search tree operation (search/insert) costs $O(h)$, where $h$ is the height. For a BST that has become a degenerate stick on $n$ keys, a search costs:

A) $O(1)$ B) $O(\log n)$ C) $O(n)$ D) $O(n \log n)$

Question 10

Which insertion order turns a binary search tree into a degenerate $O(n)$ stick?

A) a random permutation of the keys B) the keys in already-sorted order C) inserting the median first D) any order produces the same shape

Question 11

In an array-backed binary heap with the root at index 0, the parent of the node at index $i$ (for $i \ge 1$) is at index:

A) $2i + 1$ B) $2i + 2$ C) $\lfloor (i-1)/2 \rfloor$ D) $i - 1$

Question 12

A (min-) heap is a complete binary tree in which:

A) the left subtree's keys are all smaller than the right subtree's B) every node's key is $\le$ both of its children's keys C) the keys are stored in sorted order by index D) every internal node has exactly two children

Question 13

The postfix (Reverse Polish) form of an expression is produced by which traversal of its expression tree?

A) preorder B) inorder C) postorder D) level-order

Question 14

A trie lookup of a string of length $m$ takes time:

A) $O(\log N)$ where $N$ is the number of stored words B) $O(N)$ C) $O(m)$, independent of the number of stored words D) $O(m \cdot N)$

Question 15

In a prefix code represented as a binary tree, the symbols sit at:

A) the root only B) internal nodes C) leaves only D) any nodes, as long as no two share a depth

Question 16

Huffman's algorithm repeatedly merges:

A) the two trees of largest frequency B) the two trees of smallest frequency C) the leftmost two trees in insertion order D) a random pair of trees

Question 17 (True/False, justify)

True or false: A graph that is acyclic and has exactly $n - 1$ edges must be connected (hence a tree). Justify in one sentence.

Question 18 (True/False, justify)

True or false: Knowing only the inorder traversal of a binary tree is enough to reconstruct the tree uniquely. Justify in one sentence.

Question 19 (Short answer)

State the proof technique used to show "a tree on $n$ vertices has exactly $n - 1$ edges," and name the single creative step that makes the induction work.

Question 20 (Short answer)

In one sentence, explain why a symbol must never be placed at an internal node of a prefix-code tree.

Answer Key

Topics to review by question